Submission #793017

#	Time	Username	Problem	Language	Result	Execution time	Memory
793017		MODDI	Gondola (IOI14_gondola)	C++17	100 / 100	17 ms	3120 KiB

gondola

    #include "gondola.h"
    //#include "grader.cpp"
    #include <bits/stdc++.h>
    using namespace std;
    #define pb push_back
    #define mp make_pair
    typedef long long ll;
    typedef pair<long long, long long> pll;
    typedef pair<int,int> pii;
    typedef vector<int> vi;
    typedef vector<ll> vl;
    int valid(int n, int inputSeq[])
    {
    	int pos = -1;
    	for(int i = 0; i < n; i++){
    		if(inputSeq[i] == 1){
    			pos = i;
    			break;
    		}
    	}
    	bool seq = true;
    	int at = 1, lim = pos;
    	while(pos < n){
    		if(inputSeq[pos] == at){
    			pos++;
    			at++;
    		}
    		else{
    			seq = false;
    			break;
    		}
    	}
    	if(!seq)	return 0;
    	pos = 0;
    	while(pos < lim){
    		if(inputSeq[pos] == at){
    			pos++;
    			at++;
    		}
    		else{
    			seq = false;
    			break;
    		}
    	}
    	if(!seq) return 0;
    	return 1;
    }
     
    int replacement(int n, int gondolaSeq[], int replacementSeq[])
    {
    	int pos = -1;
    	for(int i = 0; i < n; i++){
    		if(gondolaSeq[i] >= 1 && gondolaSeq[i] <= n){
    			pos = i;
    			break;
    		}
    	}
    	if(pos == -1){
    		vector<pii> arr(n);
    		for(int i = 0; i < n; i++){
    			arr[i] = mp(gondolaSeq[i], i);
    		}
    		sort(arr.begin(), arr.end());
    		int j = 0, rez = 0, here = 1, at = n + 1;
    		int pos = arr[0].second, need[n];
    		for(int i = pos; i < n; i++)	need[i] = here++;
    		for(int i = 0; i < pos; i++)	need[i] = here++;
    		for(int i = 0; i < (int)arr.size(); i++){
    			int where = arr[i].second, val = arr[i].first;
    			replacementSeq[j++] = need[where];
    			rez++;
    			while(at < val){
    				replacementSeq[j++] = at++;
    				rez++;
    			}
    			at++;
    		}
    		return rez;
    	}
    	else{
    		int need[n];
    		bool done[n+1];
    		memset(done, false, sizeof done);
    		int at = gondolaSeq[pos];
    		while(at <= n){
    			at++;
    			pos++; pos%=n;
    		}
    		int here = 1;
    		for(int i = pos; i < n; i++)	need[i] = here++;
    		for(int i = 0; i < pos; i++)	need[i] = here++;
    		vector<pii> arr;
    		for(int i = 0; i < n; i++){
    			if(need[i] == gondolaSeq[i])	done[need[i]] = true;
    			else{
    				arr.pb(mp(gondolaSeq[i], i));
    			}
    		}
    		sort(arr.begin(), arr.end());
    		at = n + 1;
    		int j = 0, rez = 0;
    		for(int i = 0; i < (int)arr.size(); i++){
    			int where = arr[i].second, val = arr[i].first;
    			replacementSeq[j++] = need[where];
    			rez++;
    			while(at < val){
    				replacementSeq[j++] = at++;
    				rez++;
    			}
    			at++;
    		}
    		return rez;
    	}
    }
    const int mod = 1000000009;
    int mul(ll a, ll b){
		int res = (a*b) % mod;
		if(res < 0)	res += mod;
		return res;
	}
	int pow(int a, int b){
		int res = 1;
		while(b){
			if(b&1){
				b--;
				res = mul(res, a);
			}
			else{
				b >>= 1;
				a = mul(a,a);
			}
		}
		return res;
	}
    int countReplacement(int n, int inputSeq[])
    {
    	//int checker = valid(n, inputSeq);
    	vector<pii> arr;
    	int pos = -1;
    	for(int i = 0; i < n; i++){
    		arr.pb(mp(inputSeq[i], i));
    		if(inputSeq[i] >= 1 && inputSeq[i] <= n)	pos = i;
    	}
    	if(pos != -1){
    		int at = inputSeq[pos];
    		while(at <= n){
    			at++;
    			pos++;
    			pos%=n;
    		}
    		int skipped = 0;
    		at=1;
    		bool ok = true;
    		for(int i = pos; i < n; i++){
    			if(inputSeq[i] == at+skipped){
    				at++;
    				skipped = 0;
    			}
    			else if(inputSeq[i] <= n && at + skipped > inputSeq[i]){
    				ok = false;
    			}
    			else
    				skipped++;
    		}
    		//cout<<"OK: "<<ok<<endl;
    		if(!ok)	return 0;
    	}
    	ll ways = 1;
    	if(pos == -1)	ways = n;
    	vi niz;
    	for(int i = 0; i < n; i++)
			if(inputSeq[i] > n)	niz.pb(inputSeq[i]);
			
		sort(niz.begin(), niz.end());
		int sz = (int)niz.size(), last = n;
		for(int i : niz){
			ways = mul(ways, pow(sz, i - last - 1));
			last = i;
			sz--;
		}
		return ways;
    }

• Subtask 1: 5 / 5
• Subtask 2: 5 / 5
• Subtask 3: 10 / 10
• Subtask 4: 5 / 5
• Subtask 5: 10 / 10
• Subtask 6: 20 / 20
• Subtask 7: 5 / 5
• Subtask 8: 15 / 15
• Subtask 9: 15 / 15
• Subtask 10: 10 / 10