oj.uz

Submission #793009

# Submission time Handle Problem Language Result Execution time Memory
793009 2023-07-25T12:22:35 Z MODDI Gondola (IOI14_gondola) C++17
55 / 100
 15 ms 2252 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;
    ll calculate(ll step, ll base){
    	ll res = 1;
    	base %= mod;
    	if(base == 0)	return 0;
    	while(step > 0){
    		if(step & 1)
    			res = (res * base) % mod;
    			
    		step = step>>1;
    		base = (base*base) % mod;
    	}
    	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;
    	}
    	vi niz;
    	int where = n+1;
    	for(int i = 0; i < n; i++){
    		if(inputSeq[i] > n)	niz.pb(inputSeq[i]);
    	}
    	sort(niz.begin(), niz.end());
    	ll ways = 1;
    	for(int i = 0; i < (int)niz.size(); i++){
			if(i == 0 && niz[i] > n)	ways = n;
    		while(where < niz[i]){
    			ways *= ((int)niz.size()-i)*1LL;
    			ways %= mod;
    			where++;
    		}
    		if(where == niz[i])	where++;
    	}
    	return (int)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 212 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 1 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 1 ms 212 KB Output is correct
6 Correct 3 ms 340 KB Output is correct
7 Correct 6 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

Subtask #3
10.0 / 10.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 1 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 6 ms 596 KB Output is correct
8 Correct 7 ms 580 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 5 ms 468 KB Output is correct
14 Correct 0 ms 212 KB Output is correct
15 Correct 6 ms 604 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 1 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 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 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 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 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 980 KB Output is correct
12 Correct 7 ms 980 KB Output is correct
13 Correct 10 ms 1408 KB Output is correct
14 Correct 6 ms 980 KB Output is correct
15 Correct 15 ms 2252 KB Output is correct

Subtask #7
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #8
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #9
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #10
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -