oj.uz

Submission #793017

# Submission time Handle Problem Language Result Execution time Memory
793017 2023-07-25T12:27:09 Z MODDI Gondola (IOI14_gondola) C++17
100 / 100
 17 ms 3120 KB 
    #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.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 344 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 4 ms 340 KB Output is correct
7 Correct 7 ms 596 KB Output is correct
8 Correct 5 ms 596 KB Output is correct
9 Correct 2 ms 340 KB Output is correct
10 Correct 6 ms 596 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 3 ms 340 KB Output is correct
7 Correct 7 ms 596 KB Output is correct
8 Correct 5 ms 468 KB Output is correct
9 Correct 2 ms 340 KB Output is correct
10 Correct 6 ms 596 KB Output is correct
11 Correct 0 ms 212 KB Output is correct
12 Correct 0 ms 212 KB Output is correct
13 Correct 3 ms 340 KB Output is correct
14 Correct 0 ms 212 KB Output is correct
15 Correct 6 ms 596 KB Output is correct

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct

Subtask #6
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 280 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 6 ms 964 KB Output is correct
12 Correct 8 ms 980 KB Output is correct
13 Correct 10 ms 1380 KB Output is correct
14 Correct 7 ms 960 KB Output is correct
15 Correct 15 ms 2240 KB Output is correct

Subtask #7
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct

Subtask #8
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct

Subtask #9
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 13 ms 1660 KB Output is correct
10 Correct 9 ms 1356 KB Output is correct
11 Correct 4 ms 724 KB Output is correct
12 Correct 6 ms 880 KB Output is correct
13 Correct 1 ms 340 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 11 ms 1700 KB Output is correct
10 Correct 9 ms 1356 KB Output is correct
11 Correct 4 ms 724 KB Output is correct
12 Correct 5 ms 848 KB Output is correct
13 Correct 1 ms 340 KB Output is correct
14 Correct 15 ms 2840 KB Output is correct
15 Correct 17 ms 3120 KB Output is correct
16 Correct 3 ms 852 KB Output is correct
17 Correct 11 ms 2108 KB Output is correct
18 Correct 6 ms 1484 KB Output is correct