Submission #964535

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
964535	2024-04-17T05:19:50 Z	UmairAhmadMirza	Gondola (IOI14_gondola)	C++14	100 / 100	52 ms	6480 KB

gondola

#include <bits/stdc++.h>
#include <gondola.h>
using namespace std;
int const mod=1e9+9;
long long power(long long a,long long b){
	if(b==0)
		return 1;
	if(b==1)
		return a;
	long long pw=power(a,b/2);
	pw%=mod;
	pw*=pw;
	pw%=mod;
	if(b&1)
		pw*=a;
	pw%=mod;
	return pw;
}
int valid(int n, int inputSeq[]){
	map<int,bool> mp;
	deque<int> d;
	int k=n+1;
	for (int i = 0; i < n; ++i)//check unique
	{
		d.push_back(inputSeq[i]);
		if(mp[inputSeq[i]]){

			return 0;
		}
		mp[inputSeq[i]]=1;
		k=min(k,inputSeq[i]);
	}
	if(k==n+1)
		return 1;
	while(d[k-1]!=k){
		d.push_front(d.back());
		d.pop_back();
		// cerr<<"1"<<endl;
	}
	// cerr<<"1"<<endl;
	for (int i = 0; i < n; ++i)
		if(d[i]<=n && d[i]!=i+1)
			return 0;
	return 1;
}
int replacement(int n, int gondolaSeq[], int replacementSeq[]){
	int maxa=0;
	for (int i = 0; i < n; ++i)
		maxa=max(gondolaSeq[i],maxa);
	int k=n+1;
	deque<int> d;
	for (int i = 0; i < n; ++i)//check unique
	{
		d.push_back(gondolaSeq[i]);
		k=min(k,gondolaSeq[i]);
	}
	if(k<n+1){
		while(d[k-1]!=k){
			d.push_front(d.back());
			d.pop_back();
		}
		// cerr<<"set"<<endl;
	}
	int c=0;
	set<pair<int,int>> s;
	for (int i = 0; i < n; ++i)
		if(d[i]>n)
			s.insert({d[i],i+1});
	while(s.size()){
		auto p=*(s.begin());
		int dd=p.first;
		int cur=p.second;
		s.erase(p);
		while(cur<dd){
			replacementSeq[c]=cur;
			c++;
			cur=n+c;
		}
	}
	return c;
}
int countReplacement(int n, int inputSeq[]){
	if(valid(n,inputSeq)==0)
		return 0;
	vector<long long> v;
	long long ans=1;
	for (int i = 0; i < n; ++i)
		if(inputSeq[i]>n)
			v.push_back(inputSeq[i]);
	sort(v.begin(), v.end());
	long long cur=n;
	int sz=v.size();
	if(sz==n)
		ans=sz;
	for (int i = 0; i < sz; ++i)
	{
		// cout<<sz-i<<' '<<(v[i]-cur)-1<<endl;
		ans*=power(sz-i,(v[i]-cur)-1)%mod;
		ans%=mod;
		cur=v[i];
	}
	return ans%mod;
}

Subtask #1
5.0 / 5.0

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

Subtask #2
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	348 KB	Output is correct
2	Correct	1 ms	348 KB	Output is correct
3	Correct	1 ms	440 KB	Output is correct
4	Correct	1 ms	396 KB	Output is correct
5	Correct	0 ms	348 KB	Output is correct
6	Correct	9 ms	2500 KB	Output is correct
7	Correct	7 ms	1116 KB	Output is correct
8	Correct	21 ms	4660 KB	Output is correct
9	Correct	6 ms	1732 KB	Output is correct
10	Correct	19 ms	5460 KB	Output is correct

Subtask #3
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	344 KB	Output is correct
2	Correct	1 ms	444 KB	Output is correct
3	Correct	0 ms	348 KB	Output is correct
4	Correct	1 ms	344 KB	Output is correct
5	Correct	1 ms	348 KB	Output is correct
6	Correct	8 ms	2540 KB	Output is correct
7	Correct	8 ms	1372 KB	Output is correct
8	Correct	18 ms	4700 KB	Output is correct
9	Correct	6 ms	1628 KB	Output is correct
10	Correct	19 ms	5316 KB	Output is correct
11	Correct	0 ms	348 KB	Output is correct
12	Correct	0 ms	348 KB	Output is correct
13	Correct	19 ms	2404 KB	Output is correct
14	Correct	1 ms	348 KB	Output is correct
15	Correct	34 ms	5432 KB	Output is correct

Subtask #4
5.0 / 5.0

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

Subtask #5
10.0 / 10.0

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

Subtask #6
20.0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	344 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	0 ms	344 KB	Output is correct
4	Correct	1 ms	348 KB	Output is correct
5	Correct	0 ms	348 KB	Output is correct
6	Correct	1 ms	348 KB	Output is correct
7	Correct	1 ms	348 KB	Output is correct
8	Correct	1 ms	348 KB	Output is correct
9	Correct	1 ms	348 KB	Output is correct
10	Correct	1 ms	348 KB	Output is correct
11	Correct	7 ms	1372 KB	Output is correct
12	Correct	7 ms	1536 KB	Output is correct
13	Correct	16 ms	2820 KB	Output is correct
14	Correct	7 ms	1372 KB	Output is correct
15	Correct	19 ms	3176 KB	Output is correct

Subtask #7
5.0 / 5.0

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

Subtask #8
15.0 / 15.0

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

Subtask #9
15.0 / 15.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	348 KB	Output is correct
2	Correct	0 ms	440 KB	Output is correct
3	Correct	0 ms	348 KB	Output is correct
4	Correct	1 ms	348 KB	Output is correct
5	Correct	0 ms	348 KB	Output is correct
6	Correct	1 ms	348 KB	Output is correct
7	Correct	0 ms	348 KB	Output is correct
8	Correct	0 ms	348 KB	Output is correct
9	Correct	33 ms	4784 KB	Output is correct
10	Correct	27 ms	3920 KB	Output is correct
11	Correct	11 ms	1996 KB	Output is correct
12	Correct	12 ms	1880 KB	Output is correct
13	Correct	3 ms	604 KB	Output is correct

Subtask #10
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	348 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	1 ms	344 KB	Output is correct
4	Correct	0 ms	348 KB	Output is correct
5	Correct	0 ms	348 KB	Output is correct
6	Correct	1 ms	348 KB	Output is correct
7	Correct	0 ms	348 KB	Output is correct
8	Correct	0 ms	348 KB	Output is correct
9	Correct	39 ms	4976 KB	Output is correct
10	Correct	31 ms	4184 KB	Output is correct
11	Correct	10 ms	1628 KB	Output is correct
12	Correct	13 ms	1884 KB	Output is correct
13	Correct	3 ms	600 KB	Output is correct
14	Correct	42 ms	5692 KB	Output is correct
15	Correct	52 ms	6480 KB	Output is correct
16	Correct	8 ms	1368 KB	Output is correct
17	Correct	32 ms	4436 KB	Output is correct
18	Correct	17 ms	2848 KB	Output is correct

Submission #964535

Compilation message