8. Masaker v Kratarií vzorové riešenie

4
2 1 1 2

2

6
6 3 1 1 2 2

0

7
4 3 3 1 1 1 2

18

Počet operácii

Konštanta \(K\) nech predstavuje počet jednotiek na vstupe. Ak je vstup validný, respektíve ak existuje aspoň jedna permutácia, ktorá sa po konečnom počte operácií zmení na postupnosť na vstupe, tak počet vykonaných operácií je rovno \(K-1\), pretože po každej operácií sa úsek jednotiek zväčši o jedna.

Úseky

Na základe počtu operácií sa pre každé číslo na vstupe dá určiť úsek pozícií, kde sa v pôvodnej permutácií toto číslo mohlo nachádzať. Treba si však všimnúť, že číslo sa nemohlo nachádzať na pozícii, kde do \(K\) pozícií od neho sa na vstupe nachádza väčšie číslo. Na základe tohto sa nemôžu dva úseky prekrývať, pretože by to znamenalo, že na rovnakej pozícii môžu byť dve rôzne čísla, ktoré sa v postupnosti zo vstupu nachádzajú. To by znamenalo, že do \(K\) pozícií od tejto spoločnej sa na vstupe nachádzajú obe čísla, ale pritom platí, že jedno z týchto čísel je menšie a nemôže sa teda na tejto pozícii nachádzať.

        vstup: 1 1 1 2 2 4
        úseky: 1   2 4 4 4
               1 · 1 · 3

Tieto úseky vieme nájsť jedným prechodom vstupu: Ak narazíme na prechod z väčšieho čísla na menšie, znamená to, že úsek väčšieho čísla môže začínať najskôr \(K\) pozícií pred ním a končiť najneskôr na jeho pozícii, a že úsek menšieho čísla môže začínať najskôr a končiť najneskôr na svojej pozícii. A podobne naopak, ak narazíme na prechod z menšieho na väčšie, úsek menšieho môže začínať najskôr a končiť najneskôr \(K\) pozícií pred jeho pozíciou a úsek väčšieho môže začať najskôr \(K\) pozícií pred svojou pozíciou a končiť najneskôr na svojej pozícii.

Dolné hranice

Spomínané úseky však nijako neurčujú kde sa môžu nachádzať zvyšné čísla, ktoré sa na vstupe nevyskytujú. Pre tieto čísla vieme určiť dolné hranice, teda pre každú pozíciu najmenšie číslo ktoré sa tam mohlo nachádzať v pôvodnej permutácií. Teda dolná hranica pre nejakú pozíciu je určená maximom na intervale dĺžky \(K\) začínajúcom na tejto pozícii. Toto sa dá nájsť pomocou okienkového minima.

        vstup: 1 1 1 2 2 4
        úseky: 1   2 4 4 4
dolné hranice: 1 2 2 4 4 4

Všimnime si, že pre každú pozíciu v úseku je rovnaká dolná hranica. Je to tak, pretože dolná hranica nemôže byť menšia ako číslo, ktorého je to úsek, a zároveň na týchto pozíciach môže byť aspoň to číslo. Z tohto dôvodu, keď si zvolíme niektorú možnú pozíciu pre číslo z jeho úseku, dolné hranice sa nezmenia a teda môžme voliť pozície a čísla ktoré sa na vstupe nenachádzajúcu podľa dolných hraníc nezávislo na sebe.

Potrebujeme si však ešte rozmyslieť, ako vyberať čísla, ktoré na vstupe nie sú. Môžu byť kdekoľvek, kde nie je žiaden úsek a ak tam úsek je, tak jednu (ľubovoľnú) pozíciu vynecháme, pričom musia vyhovovať dolným hraniciam. Ak by sme tieto čísla vyberali akokoľvek, mohlo by sa stať, že by pre pozície s vyššou dolnou hranicou nezostalo číslo. Keďže platí, že pre pozíciu s vyššou dolnou hranicou je na výber podmnožina čísel ako pre pozíciu s nižšou, tak môžme vyberať náhodne od pozícií s väčšou. Na to však treba tieto dolné hranice zoradiť podľa veľkosti, pričom si stačí uvedomiť, že na ne vieme použiť counting sort.

        vstup: 1 1 1 2 2 4
        úseky: 1   2 4 4 4
               1 · 1 · 3
dolné hranice: 1 2 2 4 4 4
                 3
 zvyšné čísla:   5   5 5
                 6   6 6

Výsledok je tým pádom \(1 \cdot 1 \cdot 3\) (úseky) krát \(2 \cdot 1 \cdot 1\) (zvyšné čísla), teda dokopy \(3 \cdot 2 = 6\)

Možné postupnosti:

1 3 2 4 5 6
1 3 2 4 6 5
1 3 2 5 4 6
1 3 2 6 4 5
1 3 2 5 6 4
1 3 2 6 5 4

Neplatné vstupy

Na vstupe musí byť aspoň jedna jednotka. Všetky rovnaké čísla na vstupe musia tvoriť jeden súvislý interval. Pri hľadaní úsekov, nemusí existovať neprázdny úsek alebo pri vyberaní zvyšných čísel nemusí byť možné čísla rozdeliť. V týchto prípadoch neexistuje žiadna permutácia ktorá sa po \(K-1\) operáciach zmení na zadanú postupnosť, teda výsledok je \(0\).

#include <bits/stdc++.h>
using namespace std;
#define pn 1000000007


int main() {
	
	int n; cin >> n;
	deque <int> A(n);
	int k = 0;
	for (int i = 0; i < n; i++) { // O(n)
		cin >> A[i];
		if (A[i] == 1) k++;
	}
	
	if (k == 0) {
		cout << 0 << endl;
		return 0;
	}
	
	if (k == n) { // out = n!
		uint64_t out = 1;
		for (int i = 2; i <= n; i++) out = out * i % pn;
		cout << out << endl;
		return 0;
	}
	
	while (A.front() != 1 || A.front() == A.back()) {
		A.push_front(A.back());
		A.pop_back();
	}
	A.shrink_to_fit();
	
	bool possible = true;
	vector <bool> notInA(n+1, true);
	for (int i = 1; i < n; i++) { // O(n)
		if (A[i-1] != A[i] && !notInA[A[i]]) possible = false;
		notInA[A[i]] = false;
	}
	if (!possible) {
		cout << 0 << endl;
		return 0;
	}
	
	deque <array <int, 3>> u;   // {num, left, right}
	deque <int> mxw;            // max window {pos}
	vector <int> l(n, 1); // lower bounds
	vector <int> lc(n+1);    // lc[i] - count of numbers not in A and at least i
	lc[n] = notInA[n];
	u.push_front({A.back(), n-k, n-1});
	for (int i = n-1; i >= 1; i--) {                                    // O(n)
		while (!mxw.empty() && A[mxw.front()] <= A[i]) mxw.pop_front(); // O(1)
		mxw.push_front(i);
		if (mxw.back() == i+k) mxw.pop_back();
		l[i] = A[mxw.back()];
		
		if (A[i-1] != A[i]) {
			u.front()[2] = min(u.front()[2], i);
			if (A[i-1] < A[i]) {
				u.push_front({A[i-1], i-k, i-k});
			} else if (A[i-1] > A[i]) {
				u.front()[1] = max(u.front()[1], i);
				u.push_front({A[i-1], i-k, i-1});
			}
			if (u.front()[1] > u.front()[2]) {
				cout << 0 << endl;
				return 0;
			}
		}
		
		lc[i] = lc[i+1] + notInA[i];
	}
	
	/*
	for (int i = 0; i < n; i++) cout << A[i] << ' ';
	cout << endl;
	for (int i = 0, j = 0; i < n; i++) {
		if (j < u.size() && i >= u[j][1]) {
			cout << u[j][0] << ' ';
			cout.flush();
		} else {
			cout << "  ";
		}
		if (i == u[j][2]) j++;
	}
	cout << endl;
	for (int i = 0; i < n; i++) cout << l[i] << ' ';
	cout << endl;
	*/
//	for (auto i : u) cout << i[0] << ' ' << i[1] << ' ' << i[2] << endl;
	
	uint64_t out = 1;
	vector <int> countSort(n+1, 0);
	for (int i = 0, j = 0; i < n; i++) {// |u[i]| < 0 - not possible
//		if (i == u[j][2]) out = out * max(0, u[j][2]-u[j][1]+1) % pn, j++;
		if (i == u[j][2]) {
			if (j < (int)u.size()) out = out * max(0, u[j][2]-u[j][1]+1) % pn, j++;
		} else countSort[lc[l[i]]]++;
	}
//	for (int i = 0; i < n+1; i++) cout << i << ' ' << lc[i] << ' ' << countSort[i] << endl;
	for (int i = 0, removed = 0; i < (int)countSort.size() && out; i++) { // O(n - |u|)
		while (countSort[i]) {
			out = out * (i-removed) % pn;
			countSort[i]--, removed++;
		}
	}
	
	cout << out << endl;
	
	return 0;
}