oj.uz

Submission #792996

# Submission time Handle Problem Language Result Execution time Memory
792996 2023-07-25T12:14:32 Z MODDI Gondola (IOI14_gondola) C++17
75 / 100
 15 ms 2304 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 = 1e9 + 9;
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++){
		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 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 3 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 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 572 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 8 ms 564 KB Output is correct

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 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 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 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 256 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 944 KB Output is correct
12 Correct 7 ms 1016 KB Output is correct
13 Correct 10 ms 1396 KB Output is correct
14 Correct 6 ms 864 KB Output is correct
15 Correct 15 ms 2304 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 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 0 ms 212 KB Output is correct

Subtask #9
0 / 15.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 1 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 1696 KB Output is correct
10 Correct 12 ms 1448 KB Output is correct
11 Correct 4 ms 724 KB Output is correct
12 Correct 5 ms 784 KB Output is correct
13 Incorrect 2 ms 340 KB Output isn't correct
14 Halted 0 ms 0 KB -

Subtask #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 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 11 ms 1696 KB Output is correct
10 Correct 9 ms 1356 KB Output is correct
11 Correct 5 ms 724 KB Output is correct
12 Correct 5 ms 880 KB Output is correct
13 Incorrect 3 ms 448 KB Output isn't correct
14 Halted 0 ms 0 KB -