oj.uz

Submission #73529

# Submission time Handle Problem Language Result Execution time Memory
73529 2018-08-28T11:35:48 Z TuGSGeReL Gondola (IOI14_gondola) C++14
100 / 100
 119 ms 8088 KB 
#include "gondola.h"
#include<bits/stdc++.h>
#define ll long long 
#define mp make_pair
#define pub push_back
#define pob pop_back
#define ss second
#define ff first
#define ext exit(0)
using namespace std;
ll i,j,z=0,st,ans;
vector<ll> vc,vv;
vector<pair<ll,ll> >v;
map<ll,ll>m;
int valid(int n, int inputSeq[])
{
	for(i=0;i<n;i++){
		if(m[inputSeq[i]]==1) return 0;
		m[inputSeq[i]]++;
	}
	for(i=0;i<n;i++){
		if(inputSeq[i]<n){
			st=(i-inputSeq[i]+1+n)%n;
			for(i=st;i<n;i++) vv.pub(inputSeq[i]);
			for(i=0;i<st;i++) vv.pub(inputSeq[i]);
			for(i=0;i<n;i++){
				if(vv[i]>n) continue;
				if(vv[i]!=i+1) return 0;
			}
			return 1;
		}
	}
	return 1;
}
int replacement(int n, int gondolaSeq[], int replacementSeq[]) {
	for(i=0;i<n;i++) gondolaSeq[i]--;
	
	for(i=0;i<n;i++){
		if(gondolaSeq[i] < n){
			st=(i-gondolaSeq[i]+n)%n;
		}
	}
	for(i=0;i<n;i++){
		if(gondolaSeq[i] >= n) v.pub(mp(gondolaSeq[i],(i-st+n)%n));
	}
	sort(v.begin(),v.end());
	if(v.size()==0) {
		return 0;
	}
	while(1){
		if(v.size()==1){
			while(v[0].ff>v[0].ss && v[0].ff>=n){
				if(v[0].ff-1>=n)vc.pub(v[0].ff-1);
				else vc.pub(v[0].ss);
				v[0].ff--;
			}
			break;
		}
		if(v.back().ff==v[v.size()-2].ff+1){
			vc.pub(v.back().ss);
			v.pob();
		}
		else {
			vc.pub(v.back().ff-1);
			v.back().ff--;
			if(v.back().ff==v.back().ss) v.pob();
		}
	}
	reverse(vc.begin(),vc.end());
	for(i=0;i<vc.size();i++) replacementSeq[i]=vc[i]+1;
	return vc.size();
}
int countReplacement(int n, int inputSeq[]) {
	if(!valid(n,inputSeq)) return 0;
	bool boo=false;
	for(i=0;i<n;i++){
		if(inputSeq[i]>n)vc.pub(inputSeq[i]);
		else boo=true;
	}
	sort(vc.begin(),vc.end());
	ll prev=n+1,ans=1,mod=1000000009;
	for(i=0;i<vc.size();i++){
		ll o=vc.size()-i,s=1,u=vc[i]-prev;
		while(u>0){
			if(u%2){
				s=(ll)(s*o)%mod;
			}
			o=(ll)(o*o)%mod;
			u/=2;
		}
		ans=(ll)(ans*s)%mod;
		prev=vc[i]+1;
	}
	if(!boo) ans=(ll)(ans*n)%mod;
	return ans;
}

Compilation message

gondola.cpp: In function 'int replacement(int, int*, int*)':
gondola.cpp:70:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(i=0;i<vc.size();i++) replacementSeq[i]=vc[i]+1;
          ~^~~~~~~~~~
gondola.cpp: In function 'int countReplacement(int, int*)':
gondola.cpp:82:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(i=0;i<vc.size();i++){
          ~^~~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 248 KB Output is correct
2 Correct 3 ms 484 KB Output is correct
3 Correct 3 ms 484 KB Output is correct
4 Correct 3 ms 512 KB Output is correct
5 Correct 2 ms 512 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 688 KB Output is correct
2 Correct 2 ms 688 KB Output is correct
3 Correct 3 ms 688 KB Output is correct
4 Correct 4 ms 688 KB Output is correct
5 Correct 3 ms 688 KB Output is correct
6 Correct 27 ms 3664 KB Output is correct
7 Correct 17 ms 3664 KB Output is correct
8 Correct 59 ms 6496 KB Output is correct
9 Correct 17 ms 6496 KB Output is correct
10 Correct 62 ms 7260 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 7260 KB Output is correct
2 Correct 2 ms 7260 KB Output is correct
3 Correct 2 ms 7260 KB Output is correct
4 Correct 3 ms 7260 KB Output is correct
5 Correct 2 ms 7260 KB Output is correct
6 Correct 26 ms 7260 KB Output is correct
7 Correct 18 ms 7260 KB Output is correct
8 Correct 53 ms 7260 KB Output is correct
9 Correct 20 ms 7260 KB Output is correct
10 Correct 69 ms 7340 KB Output is correct
11 Correct 2 ms 7340 KB Output is correct
12 Correct 2 ms 7340 KB Output is correct
13 Correct 30 ms 7340 KB Output is correct
14 Correct 2 ms 7340 KB Output is correct
15 Correct 92 ms 7392 KB Output is correct

Subtask #4
5.0 / 5.0

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

Subtask #5
10.0 / 10.0

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

Subtask #6
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 7392 KB Output is correct
2 Correct 2 ms 7392 KB Output is correct
3 Correct 3 ms 7392 KB Output is correct
4 Correct 3 ms 7392 KB Output is correct
5 Correct 2 ms 7392 KB Output is correct
6 Correct 2 ms 7392 KB Output is correct
7 Correct 2 ms 7392 KB Output is correct
8 Correct 3 ms 7392 KB Output is correct
9 Correct 3 ms 7392 KB Output is correct
10 Correct 3 ms 7392 KB Output is correct
11 Correct 18 ms 7392 KB Output is correct
12 Correct 18 ms 7392 KB Output is correct
13 Correct 22 ms 7392 KB Output is correct
14 Correct 17 ms 7392 KB Output is correct
15 Correct 36 ms 7392 KB Output is correct

Subtask #7
5.0 / 5.0

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

Subtask #8
15.0 / 15.0

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

Subtask #9
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 7392 KB Output is correct
2 Correct 2 ms 7392 KB Output is correct
3 Correct 2 ms 7392 KB Output is correct
4 Correct 3 ms 7392 KB Output is correct
5 Correct 3 ms 7392 KB Output is correct
6 Correct 4 ms 7392 KB Output is correct
7 Correct 2 ms 7392 KB Output is correct
8 Correct 3 ms 7392 KB Output is correct
9 Correct 85 ms 7392 KB Output is correct
10 Correct 68 ms 7392 KB Output is correct
11 Correct 26 ms 7392 KB Output is correct
12 Correct 35 ms 7392 KB Output is correct
13 Correct 8 ms 7392 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 7392 KB Output is correct
2 Correct 3 ms 7392 KB Output is correct
3 Correct 3 ms 7392 KB Output is correct
4 Correct 3 ms 7392 KB Output is correct
5 Correct 3 ms 7392 KB Output is correct
6 Correct 2 ms 7392 KB Output is correct
7 Correct 2 ms 7392 KB Output is correct
8 Correct 3 ms 7392 KB Output is correct
9 Correct 103 ms 7392 KB Output is correct
10 Correct 73 ms 7392 KB Output is correct
11 Correct 31 ms 7392 KB Output is correct
12 Correct 41 ms 7392 KB Output is correct
13 Correct 8 ms 7392 KB Output is correct
14 Correct 119 ms 7448 KB Output is correct
15 Correct 114 ms 8088 KB Output is correct
16 Correct 20 ms 8088 KB Output is correct
17 Correct 110 ms 8088 KB Output is correct
18 Correct 45 ms 8088 KB Output is correct