oj.uz

Submission #38838

# Submission time Handle Problem Language Result Execution time Memory
38838 2018-01-07T05:29:49 Z adamczh1 Gondola (IOI14_gondola) C++14
100 / 100
 139 ms 8928 KB 
#include "gondola.h"
#include <bits/stdc++.h>
using namespace std;

int valid(int n, int inputSeq[])
{
	set<int> s;
	set<int> t;
	for(int i=0;i<n;i++){
		if(inputSeq[i]<=n){
			s.insert((i-inputSeq[i]+n)%n);
		}
		t.insert(inputSeq[i]);
	}
	return s.size()<=1 && t.size()==n;
}

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

int replacement(int n, int gondolaSeq[], int replacementSeq[])
{
	set<int> s;
	vector<int> loc(250001,-1);
	for(int i=0;i<n;i++){
		if(gondolaSeq[i]<=n){
			s.insert((i-gondolaSeq[i]+n)%n);
		}
		loc[gondolaSeq[i]]=i;
	}
	int l=0;
	int cur=n+1;
	if(s.size()==0){
		for(int i=1;i<=250000;i++){
			if(loc[i]==-1)continue;
			replacementSeq[l]=loc[i]+1;
			l++;
			cur++;
			while(cur<=i){
				replacementSeq[l]=cur-1;
				l++;
				cur++;
			}
		}
	}
	else{
		int dif=*s.begin();
		for(int i=n+1;i<=250000;i++){
			if(loc[i]==-1)continue;
			int tmp=(loc[i]-dif+n)%n;
			if(tmp==0)tmp=n;
			replacementSeq[l]=tmp;
			l++;
			cur++;
			while(cur<=i){
				replacementSeq[l]=cur-1;
				l++;
				cur++;
			}
		}
	}
	return l;
}

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

int fpow(int a,int b,int mod){
	if(b==0) return 1;
	if(b&1) return 1ll*fpow(a,b-1,mod)*a%mod;
	int tmp=fpow(a,b>>1,mod);
	return 1ll*tmp*tmp%mod;
}

int countReplacement(int n, int inputSeq[])
{
	int MOD=1e9+9;
	if(!valid(n,inputSeq)) return 0;
	set<int> s;
	for(int i=0;i<n;i++){
		if(inputSeq[i]>n){
			s.insert(inputSeq[i]);
		}
	}
	int x=s.size();
	int cur=n;
	long long ans=1;
	for(int val:s){
		ans*=fpow(x,val-cur-1,MOD);
		ans%=MOD;
		cur=val;
		x--;
	}
	if(s.size()==n){
		ans*=n;
		ans%=MOD;
	}
	return ans;
}

Compilation message

gondola.cpp: In function 'int valid(int, int*)':
gondola.cpp:15:32: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  return s.size()<=1 && t.size()==n;
                                ^
gondola.cpp: In function 'int countReplacement(int, int*)':
gondola.cpp:92:13: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  if(s.size()==n){
             ^

Subtask #1
5.0 / 5.0

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

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 3384 KB Output is correct
2 Correct 0 ms 3384 KB Output is correct
3 Correct 0 ms 3384 KB Output is correct
4 Correct 0 ms 3384 KB Output is correct
5 Correct 0 ms 3384 KB Output is correct
6 Correct 13 ms 5100 KB Output is correct
7 Correct 59 ms 7740 KB Output is correct
8 Correct 26 ms 6684 KB Output is correct
9 Correct 3 ms 4440 KB Output is correct
10 Correct 39 ms 7344 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 3384 KB Output is correct
2 Correct 0 ms 3384 KB Output is correct
3 Correct 0 ms 3384 KB Output is correct
4 Correct 0 ms 3384 KB Output is correct
5 Correct 0 ms 3384 KB Output is correct
6 Correct 16 ms 5100 KB Output is correct
7 Correct 63 ms 7740 KB Output is correct
8 Correct 23 ms 6684 KB Output is correct
9 Correct 6 ms 4440 KB Output is correct
10 Correct 26 ms 7344 KB Output is correct
11 Correct 0 ms 3384 KB Output is correct
12 Correct 0 ms 3384 KB Output is correct
13 Correct 16 ms 5100 KB Output is correct
14 Correct 0 ms 3384 KB Output is correct
15 Correct 69 ms 8928 KB Output is correct

Subtask #4
5.0 / 5.0

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

Subtask #5
10.0 / 10.0

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

Subtask #6
20.0 / 20.0

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

Subtask #7
5.0 / 5.0

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

Subtask #8
15.0 / 15.0

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

Subtask #9
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 3384 KB Output is correct
2 Correct 0 ms 3384 KB Output is correct
3 Correct 0 ms 3384 KB Output is correct
4 Correct 0 ms 3384 KB Output is correct
5 Correct 0 ms 3384 KB Output is correct
6 Correct 0 ms 3384 KB Output is correct
7 Correct 0 ms 3384 KB Output is correct
8 Correct 0 ms 3384 KB Output is correct
9 Correct 63 ms 6816 KB Output is correct
10 Correct 49 ms 6288 KB Output is correct
11 Correct 19 ms 4440 KB Output is correct
12 Correct 26 ms 4704 KB Output is correct
13 Correct 3 ms 3648 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 3384 KB Output is correct
2 Correct 0 ms 3384 KB Output is correct
3 Correct 0 ms 3384 KB Output is correct
4 Correct 0 ms 3384 KB Output is correct
5 Correct 0 ms 3384 KB Output is correct
6 Correct 0 ms 3384 KB Output is correct
7 Correct 0 ms 3384 KB Output is correct
8 Correct 0 ms 3384 KB Output is correct
9 Correct 66 ms 6816 KB Output is correct
10 Correct 53 ms 6288 KB Output is correct
11 Correct 19 ms 4440 KB Output is correct
12 Correct 19 ms 4704 KB Output is correct
13 Correct 3 ms 3648 KB Output is correct
14 Correct 119 ms 7344 KB Output is correct
15 Correct 139 ms 7872 KB Output is correct
16 Correct 13 ms 4176 KB Output is correct
17 Correct 83 ms 6420 KB Output is correct
18 Correct 46 ms 5100 KB Output is correct