Submission #278114

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
278114	2020-08-21T10:43:30 Z	amiratou	Gondola (IOI14_gondola)	C++14	75 / 100	71 ms	5624 KB

gondola

#include "gondola.h"
#include <bits/stdc++.h>
using namespace std;
#define sz(x) (int)(x.size())
const int MOD =(int)(1e9+9);
typedef long long ll;
int val[100005],p[250005],dp[100005][2];
set<int> here;

int valid(int n, int inputSeq[])
{
	int idx=-1;
	for (int i = 0; i < n; ++i){
		if(here.find(inputSeq[i])!=here.end())return 0;
		here.insert(inputSeq[i]);
		if(inputSeq[i]<=n)idx=i;
	}
	if(idx==-1)return 1;
	int h=inputSeq[idx];
	for (int i = 0; i < n; ++i)
		val[(idx+i)%n]=((h-1+i)%n)+1;
	for (int i = 0; i < n; ++i)
		if(inputSeq[i]<=n && inputSeq[i]!=val[i])return 0;
	return 1;
}

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

int replacement(int n, int gondolaSeq[], int replacementSeq[])
{
	int flag=-1;
	for (int i = 0; i < n; ++i)
		if(gondolaSeq[i]<=n)flag=i;
	priority_queue<int,vector<int>,greater<int> > pq;
	if(flag!=-1){
		int g=gondolaSeq[flag];
		for (int i = 0; i < n; ++i){
			int r=((g-1+i)%n)+1;
			if(gondolaSeq[(flag+i)%n]!=r)pq.push(gondolaSeq[(flag+i)%n]),p[gondolaSeq[(flag+i)%n]]=r;
		}
	}
	else{
		for (int i = 0; i < n; ++i)
			p[gondolaSeq[i]]=i+1,pq.push(gondolaSeq[i]);
	}
	int h=n+1,idx=0;
	while(!pq.empty()){
		int f=pq.top();
		pq.pop();
		replacementSeq[idx++]=p[f];
		while(h<f)replacementSeq[idx++]=h++;
		h++;
	}
	return idx;
}

//----------------------
int binpow(int a,int b){
	if(!b)return 1;
	ll h=binpow(a,b>>1);
	h*=h;
	if(h>=MOD)h%=MOD;
	if(b&1)h*=a;
	if(h>=MOD)h%=MOD;
	return (int)(h);
}

int countReplacement(int n, int inputSeq[])
{
	if(!valid(n,inputSeq))return 0;
	int idx=-1;
	for (int i = 0; i < n; ++i)
		if(inputSeq[i]<=n)idx=i;
	if(idx==-1)return 1;
	int h=inputSeq[idx];
	for (int i = 0; i < n; ++i)
		val[(idx+i)%n]=((h-1+i)%n)+1;
	vector<int> vec={n};
	for (int i = 0; i < n; ++i)
		if(inputSeq[i]>n)
			vec.push_back(inputSeq[i]);
	ll ans=1;
	sort(vec.begin(),vec.end());
	for (int i = 1; i < sz(vec); ++i)
		ans=(ans*binpow(sz(vec)-i,vec[i]-vec[i-1]-1))%MOD;
	return ans;
}

Subtask #1
5.0 / 5.0

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

Subtask #2
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	384 KB	Output is correct
2	Correct	1 ms	384 KB	Output is correct
3	Correct	1 ms	288 KB	Output is correct
4	Correct	1 ms	384 KB	Output is correct
5	Correct	1 ms	384 KB	Output is correct
6	Correct	15 ms	2560 KB	Output is correct
7	Correct	14 ms	1152 KB	Output is correct
8	Correct	32 ms	4736 KB	Output is correct
9	Correct	11 ms	1664 KB	Output is correct
10	Correct	41 ms	5376 KB	Output is correct

Subtask #3
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	384 KB	Output is correct
2	Correct	1 ms	384 KB	Output is correct
3	Correct	1 ms	384 KB	Output is correct
4	Correct	0 ms	384 KB	Output is correct
5	Correct	1 ms	384 KB	Output is correct
6	Correct	16 ms	2560 KB	Output is correct
7	Correct	14 ms	1152 KB	Output is correct
8	Correct	30 ms	4604 KB	Output is correct
9	Correct	9 ms	1664 KB	Output is correct
10	Correct	36 ms	5368 KB	Output is correct
11	Correct	1 ms	384 KB	Output is correct
12	Correct	0 ms	384 KB	Output is correct
13	Correct	22 ms	2560 KB	Output is correct
14	Correct	1 ms	384 KB	Output is correct
15	Correct	58 ms	5624 KB	Output is correct

Subtask #4
5.0 / 5.0

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

Subtask #5
10.0 / 10.0

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

Subtask #6
20.0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	416 KB	Output is correct
2	Correct	1 ms	384 KB	Output is correct
3	Correct	0 ms	384 KB	Output is correct
4	Correct	0 ms	384 KB	Output is correct
5	Correct	1 ms	384 KB	Output is correct
6	Correct	0 ms	384 KB	Output is correct
7	Correct	1 ms	384 KB	Output is correct
8	Correct	1 ms	384 KB	Output is correct
9	Correct	1 ms	384 KB	Output is correct
10	Correct	1 ms	384 KB	Output is correct
11	Correct	13 ms	896 KB	Output is correct
12	Correct	14 ms	1024 KB	Output is correct
13	Correct	19 ms	1800 KB	Output is correct
14	Correct	17 ms	896 KB	Output is correct
15	Correct	28 ms	2876 KB	Output is correct

Subtask #7
5.0 / 5.0

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

Subtask #8
15.0 / 15.0

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

Subtask #9
0 / 15.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	384 KB	Output is correct
2	Correct	1 ms	384 KB	Output is correct
3	Correct	0 ms	384 KB	Output is correct
4	Correct	1 ms	384 KB	Output is correct
5	Correct	1 ms	384 KB	Output is correct
6	Correct	1 ms	384 KB	Output is correct
7	Correct	1 ms	384 KB	Output is correct
8	Correct	1 ms	384 KB	Output is correct
9	Correct	55 ms	5072 KB	Output is correct
10	Correct	41 ms	4344 KB	Output is correct
11	Correct	15 ms	1920 KB	Output is correct
12	Correct	19 ms	2304 KB	Output is correct
13	Incorrect	3 ms	640 KB	Output isn't correct

Subtask #10
0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	384 KB	Output is correct
2	Correct	1 ms	384 KB	Output is correct
3	Correct	0 ms	384 KB	Output is correct
4	Correct	1 ms	384 KB	Output is correct
5	Correct	1 ms	384 KB	Output is correct
6	Correct	1 ms	384 KB	Output is correct
7	Correct	1 ms	384 KB	Output is correct
8	Correct	1 ms	384 KB	Output is correct
9	Correct	71 ms	5088 KB	Output is correct
10	Correct	43 ms	4352 KB	Output is correct
11	Correct	14 ms	1920 KB	Output is correct
12	Correct	19 ms	2304 KB	Output is correct
13	Incorrect	4 ms	640 KB	Output isn't correct
14	Halted	0 ms	0 KB	-

Submission #278114

Compilation message