답안 #288177

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
288177	2020-09-01T09:35:11 Z	AKaan37	곤돌라 (IOI14_gondola)	C++17	100 / 100	36 ms	4224 KB

gondola

#include "gondola.h"

#include <bits/stdc++.h>

using namespace std;

typedef long long lo;
typedef pair< lo,lo > PII;

#define fi first
#define se second
#define mp make_pair
#define endl "\n"
#define pb push_back
#define fio() ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
#define FOR for(int i=1;i<=n;i++)
#define mid ((start+end)/2)
#define ort ((bas+son)/2)

const lo inf = 1000000000000000000;
const lo KOK = 100000;
const lo LOG = 30;
const lo li = 500005;
const lo mod = 1000000009;

int n,m,b[li],k,t,c[li];
lo cev,flag=-1;
string s;
vector<lo> v;

int valid(int n, int a[]){
	for(int i=0;i<n;i++)b[i]=a[i];
	sort(b,b+n);
	for(int i=1;i<n;i++){
		if(b[i]==b[i-1])return 0;
	}
	for(int i=0;i<n;i++){
		if(a[i]<=n){
			//~ cout<<a[i]-i<<endl;
			lo at=0;
			if(a[i]>i+1)at=i+1+(n-a[i]);
			else at=(i+1)-a[i];
			//~ cout<<at<<endl;
			if(flag==-1){
				flag=at;
			}
			else{
				if(flag!=at)return 0;
			}
		}
	}
	return 1;
}

int replacement(int n, int a[], int replacementSeq[]){
	int mx=0,ind=0,yes=0;
	memset(b,-1,sizeof(b));
	for(int i=0;i<n;i++){
		if(a[i]>mx)ind=i;
		mx=max(mx,a[i]);
		b[a[i]]=i;
		if(a[i]<=n)yes=i;
	}
	int len=0;
	int say=a[yes];
	if(say>n)say=1;
	for(int i=yes;i<n;i++){
		c[i]=(say);
		say++;
		say=say%(n+1);
		if(say==0)say=1;
	}
	for(int i=0;i<yes;i++){
		c[i]=(say);
		say++;
		say=say%(n+1);
		if(say==0)say=1;
	}
	//~ cout<<yes<<endl;
	for(int i=n+1;i<=mx;i++){
		if(~b[i]){replacementSeq[len++]=c[b[i]];c[b[i]]=i;}
		else{replacementSeq[len++]=c[ind];c[ind]=i;}
	}
	return len;
}

inline lo mul(lo x,lo y){
	return (x%mod)*(y%mod)%mod;
}

inline lo fp(lo x,lo y){
	if(y==0)return 1;
	if(y==1)return x;
	lo q=fp(x,y/2);
	q=mul(q,q);
	if(y%2)q=mul(q,x);
	return q;
}

int countReplacement(int n, int a[]){
	if(valid(n,a)==0)return 0;
	lo carp=n;
	//~ lo mx=0;
	//~ memset(b,-1,sizeof(b));
	for(lo i=0;i<n;i++){
		//~ b[a[i]]=1;
		if(a[i]<=n)carp--;
		else v.pb(a[i]);
	}
	v.pb(n);
	sort(v.begin(),v.end());
	cev=1;
	if(carp==n)cev=n;
	for(lo i=1;i<(lo)v.size();i++){
		cev=mul(cev,fp(carp,v[i]-v[i-1]-1));
		carp--;
	}
	return cev;
}

Subtask #1
5.0 / 5.0

#	결과	메모리	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 #2
5.0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	384 KB	Output is correct
2	Correct	0 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	0 ms	384 KB	Output is correct
6	Correct	9 ms	640 KB	Output is correct
7	Correct	19 ms	1024 KB	Output is correct
8	Correct	17 ms	896 KB	Output is correct
9	Correct	5 ms	512 KB	Output is correct
10	Correct	24 ms	1024 KB	Output is correct

Subtask #3
10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	384 KB	Output is correct
2	Correct	0 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	0 ms	384 KB	Output is correct
6	Correct	8 ms	640 KB	Output is correct
7	Correct	19 ms	1024 KB	Output is correct
8	Correct	13 ms	896 KB	Output is correct
9	Correct	5 ms	512 KB	Output is correct
10	Correct	20 ms	1024 KB	Output is correct
11	Correct	0 ms	384 KB	Output is correct
12	Correct	0 ms	384 KB	Output is correct
13	Correct	8 ms	640 KB	Output is correct
14	Correct	0 ms	384 KB	Output is correct
15	Correct	20 ms	1024 KB	Output is correct

Subtask #4
5.0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	2304 KB	Output is correct
2	Correct	1 ms	2304 KB	Output is correct
3	Correct	2 ms	2304 KB	Output is correct
4	Correct	1 ms	2304 KB	Output is correct
5	Correct	2 ms	2304 KB	Output is correct

Subtask #5
10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	2304 KB	Output is correct
2	Correct	1 ms	2304 KB	Output is correct
3	Correct	1 ms	2304 KB	Output is correct
4	Correct	2 ms	2304 KB	Output is correct
5	Correct	1 ms	2304 KB	Output is correct
6	Correct	2 ms	2304 KB	Output is correct
7	Correct	2 ms	2304 KB	Output is correct
8	Correct	2 ms	2304 KB	Output is correct
9	Correct	2 ms	2304 KB	Output is correct
10	Correct	2 ms	2304 KB	Output is correct

Subtask #6
20.0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	2304 KB	Output is correct
2	Correct	1 ms	2304 KB	Output is correct
3	Correct	1 ms	2304 KB	Output is correct
4	Correct	1 ms	2304 KB	Output is correct
5	Correct	1 ms	2304 KB	Output is correct
6	Correct	1 ms	2304 KB	Output is correct
7	Correct	2 ms	2304 KB	Output is correct
8	Correct	2 ms	2304 KB	Output is correct
9	Correct	2 ms	2304 KB	Output is correct
10	Correct	2 ms	2304 KB	Output is correct
11	Correct	12 ms	2944 KB	Output is correct
12	Correct	14 ms	2944 KB	Output is correct
13	Correct	15 ms	3328 KB	Output is correct
14	Correct	12 ms	2944 KB	Output is correct
15	Correct	25 ms	4224 KB	Output is correct

Subtask #7
5.0 / 5.0

#	결과	메모리	Grader output
1	Correct	384 KB	Output is correct
2	Correct	384 KB	Output is correct
3	Correct	384 KB	Output is correct

Subtask #8
15.0 / 15.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 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	0 ms	384 KB	Output is correct
5	Correct	0 ms	384 KB	Output is correct
6	Correct	0 ms	384 KB	Output is correct
7	Correct	0 ms	384 KB	Output is correct
8	Correct	0 ms	324 KB	Output is correct

Subtask #9
15.0 / 15.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	384 KB	Output is correct
2	Correct	0 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	1 ms	384 KB	Output is correct
7	Correct	1 ms	384 KB	Output is correct
8	Correct	0 ms	384 KB	Output is correct
9	Correct	23 ms	1532 KB	Output is correct
10	Correct	19 ms	1404 KB	Output is correct
11	Correct	8 ms	896 KB	Output is correct
12	Correct	9 ms	896 KB	Output is correct
13	Correct	3 ms	512 KB	Output is correct

Subtask #10
10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 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	0 ms	384 KB	Output is correct
6	Correct	1 ms	384 KB	Output is correct
7	Correct	0 ms	384 KB	Output is correct
8	Correct	0 ms	384 KB	Output is correct
9	Correct	24 ms	1528 KB	Output is correct
10	Correct	19 ms	1404 KB	Output is correct
11	Correct	8 ms	896 KB	Output is correct
12	Correct	9 ms	896 KB	Output is correct
13	Correct	2 ms	512 KB	Output is correct
14	Correct	31 ms	2928 KB	Output is correct
15	Correct	36 ms	3192 KB	Output is correct
16	Correct	7 ms	1024 KB	Output is correct
17	Correct	23 ms	2044 KB	Output is correct
18	Correct	13 ms	1660 KB	Output is correct

답안 #288177

Compilation message