oj.uz

Submission #38837

# Submission time Handle Problem Language Result Execution time Memory
38837 2018-01-07T05:27:13 Z adamczh1 Gondola (IOI14_gondola) C++14
75 / 100
 96 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--;
	}
	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;
                                ^

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 73 ms 7740 KB Output is correct
8 Correct 23 ms 6684 KB Output is correct
9 Correct 13 ms 4440 KB Output is correct
10 Correct 29 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 13 ms 5100 KB Output is correct
7 Correct 66 ms 7740 KB Output is correct
8 Correct 23 ms 6684 KB Output is correct
9 Correct 9 ms 4440 KB Output is correct
10 Correct 36 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 26 ms 5100 KB Output is correct
14 Correct 0 ms 3384 KB Output is correct
15 Correct 96 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 6 ms 4364 KB Output is correct
12 Correct 13 ms 4364 KB Output is correct
13 Correct 9 ms 4364 KB Output is correct
14 Correct 9 ms 4364 KB Output is correct
15 Correct 36 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
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 83 ms 6816 KB Output is correct
10 Correct 59 ms 6288 KB Output is correct
11 Correct 26 ms 4440 KB Output is correct
12 Correct 29 ms 4704 KB Output is correct
13 Incorrect 6 ms 3648 KB Output isn't correct

Subtask #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 89 ms 6816 KB Output is correct
10 Correct 49 ms 6288 KB Output is correct
11 Correct 23 ms 4440 KB Output is correct
12 Correct 26 ms 4704 KB Output is correct
13 Incorrect 3 ms 3648 KB Output isn't correct
14 Halted 0 ms 0 KB -