oj.uz

Submission #99729

# Submission time Handle Problem Language Result Execution time Memory
99729 2019-03-06T10:17:48 Z Retro3014 Gondola (IOI14_gondola) C++17
100 / 100
 109 ms 6648 KB 
#include "gondola.h"
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int MAX_X = 250000;

set<int> st;

int valid(int n, int inputSeq[]){
	int s = -1;
	for(int i=0; i<n; i++){
		if(st.find(inputSeq[i])!=st.end())	return false;
		st.insert(inputSeq[i]);
	}
	for(int i=0; i<n; i++){
		if(inputSeq[i]<=n){
			s = i; break;
		}
	}
	if(s==-1)	return 1;
	int idx = s, now = inputSeq[idx];
	bool tf = true;
	while(1){
		if(inputSeq[idx]<=n && inputSeq[idx]!=now){
			tf = false;
			break;
		}
		now = now%n+1; idx = (idx+1)%n;
		if(idx==s)	break;
	}
	if(tf)	return 1;
	return 0;
}

//----------------------

int loc[MAX_X+1];
int num[MAX_X+1];

int replacement(int n, int gondolaSeq[], int replacementSeq[]){
	int mx = 0;
	for(int i=0; i<n; i++) mx = max(mx, gondolaSeq[i]);
	for(int i=1; i<=mx; i++)	loc[i] = -1;
	for(int i=0; i<n; i++)	loc[gondolaSeq[i]] = i;
	int s = -1;
	for(int i=0; i<n; i++){
		if(gondolaSeq[i]<=n){
			s = i; break;
		}
	}
	if(s==-1){
		for(int i=0; i<n; i++){
			num[i] = i+1;
		}
	}
	else{
		bool tf = true;
		int idx = s, now = gondolaSeq[idx];
		while(1){
			if(gondolaSeq[idx]<=n && gondolaSeq[idx]!=now){
				tf = false; break;
			}
			idx = idx%n+1; now = now%n+1;
			if(idx==s)	break;
		}
		if(tf){
			idx = s; now = gondolaSeq[idx];
			while(1){
				num[idx] = now;
				idx = (idx+1)%n; now = now%n+1;
				if(idx==s)	break;
			}
		}else{
			idx = s; now = gondolaSeq[idx];
			while(1){
				num[idx] = now;
				idx = (idx+n-1)%n; now = (now+n-2)%n+1;
				if(idx==s)	break;
			}
		}
	}
	int idx = 0;
	int cnt = 0;
	for(int i=n+1; i<=mx; i++){
		if(loc[i]!=-1){
			replacementSeq[cnt++] = num[loc[i]];
			num[loc[i]] = i;
		}else{
			while(gondolaSeq[idx]==num[idx])	idx++;
			replacementSeq[cnt++] = num[idx];
			num[idx] = i;
		}
	}
	return cnt;
}

//----------------------

const ll DIV = 1000000009;

ll multi(ll x, ll y){
	if(y==1)	return x%DIV;
	if(y==0)	return 1;
	ll m = multi(x, y/2);
	if(y%2==1)	return (((m*m)%DIV)*x)%DIV;
	return ((m*m)%DIV);
}



vector<int> v;

int countReplacement(int n, int inputSeq[]){
	if(!valid(n, inputSeq))	return 0;
	int mx = 0;
	for(int i=0; i<n; i++) mx = max(mx, inputSeq[i]);
	for(int i=0; i<n; i++){
		v.push_back(inputSeq[i]);
	}sort(v.begin(), v.end());
	bool tf = false;
	for(int i=0; i<n; i++){
		if(inputSeq[i]<=n){
			tf = true; break;
		}
	}
	ll ans = 1;
	if(!tf)	ans = n;
	int prv = n+1;
	ll t = n;
	for(int i=0; i<v.size(); i++){
		if(v[i]<=n)	{
			t--;
			continue;
		}
		ans = (ans * multi(t, (ll)(v[i]-prv)))%DIV;
		t--;
		prv = v[i]+1;
	}
	return ans;
}

Compilation message

gondola.cpp: In function 'int countReplacement(int, int*)':
gondola.cpp:133:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0; i<v.size(); i++){
               ~^~~~~~~~~

Subtask #1
5.0 / 5.0

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

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 384 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 2 ms 384 KB Output is correct
5 Correct 2 ms 384 KB Output is correct
6 Correct 22 ms 2296 KB Output is correct
7 Correct 13 ms 640 KB Output is correct
8 Correct 37 ms 4016 KB Output is correct
9 Correct 11 ms 1536 KB Output is correct
10 Correct 42 ms 4572 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 3 ms 384 KB Output is correct
5 Correct 2 ms 384 KB Output is correct
6 Correct 17 ms 2276 KB Output is correct
7 Correct 16 ms 704 KB Output is correct
8 Correct 32 ms 4016 KB Output is correct
9 Correct 10 ms 1536 KB Output is correct
10 Correct 43 ms 4492 KB Output is correct
11 Correct 2 ms 300 KB Output is correct
12 Correct 2 ms 384 KB Output is correct
13 Correct 26 ms 2132 KB Output is correct
14 Correct 2 ms 384 KB Output is correct
15 Correct 65 ms 4728 KB Output is correct

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 2 ms 284 KB Output is correct
4 Correct 3 ms 384 KB Output is correct
5 Correct 3 ms 356 KB Output is correct

Subtask #5
10.0 / 10.0

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

Subtask #6
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 3 ms 384 KB Output is correct
3 Correct 3 ms 384 KB Output is correct
4 Correct 2 ms 384 KB Output is correct
5 Correct 2 ms 384 KB Output is correct
6 Correct 2 ms 384 KB Output is correct
7 Correct 2 ms 384 KB Output is correct
8 Correct 3 ms 384 KB Output is correct
9 Correct 3 ms 384 KB Output is correct
10 Correct 3 ms 384 KB Output is correct
11 Correct 12 ms 1280 KB Output is correct
12 Correct 21 ms 1400 KB Output is correct
13 Correct 16 ms 1664 KB Output is correct
14 Correct 15 ms 1280 KB Output is correct
15 Correct 21 ms 2944 KB Output is correct

Subtask #7
5.0 / 5.0

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

Subtask #8
15.0 / 15.0

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

Subtask #9
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 384 KB Output is correct
2 Correct 3 ms 384 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 3 ms 384 KB Output is correct
5 Correct 2 ms 384 KB Output is correct
6 Correct 2 ms 384 KB Output is correct
7 Correct 2 ms 384 KB Output is correct
8 Correct 2 ms 384 KB Output is correct
9 Correct 68 ms 5264 KB Output is correct
10 Correct 58 ms 4344 KB Output is correct
11 Correct 18 ms 1792 KB Output is correct
12 Correct 23 ms 2092 KB Output is correct
13 Correct 7 ms 768 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 384 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 3 ms 384 KB Output is correct
5 Correct 3 ms 384 KB Output is correct
6 Correct 2 ms 384 KB Output is correct
7 Correct 2 ms 384 KB Output is correct
8 Correct 3 ms 356 KB Output is correct
9 Correct 68 ms 5108 KB Output is correct
10 Correct 45 ms 4216 KB Output is correct
11 Correct 17 ms 1920 KB Output is correct
12 Correct 30 ms 2084 KB Output is correct
13 Correct 6 ms 768 KB Output is correct
14 Correct 96 ms 6060 KB Output is correct
15 Correct 109 ms 6648 KB Output is correct
16 Correct 14 ms 1592 KB Output is correct
17 Correct 56 ms 4600 KB Output is correct
18 Correct 34 ms 2944 KB Output is correct