Submission #1063806

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1063806	2024-08-18T03:33:13 Z	Edu175	Gondola (IOI14_gondola)	C++17	100 / 100	37 ms	7504 KB

gondola

#include "gondola.h"
#include <bits/stdc++.h>
#define pb push_back
#define fst first
#define snd second
#define fore(i,a,b) for(ll i=a,ioi=b;i<ioi;i++)
#define SZ(x) ((int)x.size())
#define ALL(x) x.begin(),x.end()
#define mset(a,v) memset((a),(v),sizeof(a))
#define imp(v) {for(auto fdgkj:v)cout<<fdgkj<<" ";cout<<"\n";}
using namespace std;
typedef long long ll;
typedef pair<ll,ll> ii;

void rotate(vector<ll>&a, ll x){
	rotate(a.begin(),a.begin()+x,a.end());
}

int valid(int n, int A[]){
	vector<ll>a(n);
	fore(i,0,n)a[i]=A[i]-1;
	set<ll>st;
	fore(i,0,n)st.insert(a[i]);
	if(SZ(st)<n)return 0;
	ll done=0;
	fore(i,0,n)if(!done&&a[i]<n){
		ll v=a[i];
		rotate(a,i);
		rotate(a,(n-v)%n),done=1;
	}
	if(!done)return 1;
	ll flag=1;
	fore(i,0,n){
		ll fi=a[i]>=n||a[i]==i;
		flag&=fi;
	}
	return flag;
}
int replacement(int n, int A[], int ret[]){
	vector<ll>a(n);
	fore(i,0,n)a[i]=A[i]-1;
	set<ll>st;
	fore(i,0,n)st.insert(a[i]);
	assert(SZ(st)==n);
	ll done=0;
	// imp(a);
	fore(i,0,n)if(!done&&a[i]<n){
		ll v=a[i];
		rotate(a,i);
		rotate(a,(n-v)%n),done=1;
	}
	// imp(a);
	vector<ii>b;
	fore(i,0,n)if(a[i]>=n)b.pb({a[i],i});
	fore(i,0,n)a[i]=i;
	sort(ALL(b));
	ll p=-1;
	vector<ll>res;
	if(!SZ(b))return 0;
	// for(auto [c,v]:b)cout<<c<<","<<v<<" ";;cout<<"\n";
	fore(k,n,b.back().fst+1){
		// cout<<k<<": "<<p<<endl;
		ll i=b[p+1].snd;
		res.pb(a[i]);
		a[i]=k;
		if(b[p+1].fst==k)p++;
	}
	fore(i,0,SZ(res))ret[i]=res[i]+1;
	return SZ(res);
}
const ll MOD=1e9+9;
// ll add(ll a, ll b){a+=b;if(a>=MOD)a-=MOD;return a;}
// ll sub(ll a, ll b){a-=b;if(a<0)a+=MOD;return a;}
ll mul(ll a, ll b){return a*b%MOD;}
ll fpow(ll b, ll e){
	ll res=1;
	while(e){
		if(e&1)res=mul(res,b);
		b=mul(b,b),e>>=1;
	}
	return res;
}
int countReplacement(int n, int A[]){
	vector<ll>a(n);
	fore(i,0,n)a[i]=A[i]-1;
	if(!valid(n,A))return 0;
	ll done=0;
	// imp(a);
	fore(i,0,n)if(!done&&a[i]<n){
		ll v=a[i];
		rotate(a,i);
		rotate(a,(n-v)%n),done=1;
	}
	// imp(a);
	vector<ll>b;
	fore(i,0,n)if(a[i]>=n)b.pb(a[i]);
	sort(ALL(b));
	// if(!SZ(b))return 1;
	ll res=1;
	fore(i,0,SZ(b)){
		ll dif=b[i]-(i?b[i-1]:n-1)-1;
		res=mul(res,fpow(SZ(b)-i,dif));
	}
	if(!done)res=mul(res,n);
	return res;
}

Subtask #1
5.0 / 5.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	348 KB	Output is correct
4	Correct	1 ms	348 KB	Output is correct
5	Correct	0 ms	348 KB	Output is correct

Subtask #2
5.0 / 5.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	0 ms	360 KB	Output is correct
4	Correct	0 ms	360 KB	Output is correct
5	Correct	0 ms	360 KB	Output is correct
6	Correct	8 ms	2876 KB	Output is correct
7	Correct	22 ms	4944 KB	Output is correct
8	Correct	15 ms	4956 KB	Output is correct
9	Correct	5 ms	1896 KB	Output is correct
10	Correct	21 ms	5720 KB	Output is correct

Subtask #3
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	600 KB	Output is correct
2	Correct	1 ms	348 KB	Output is correct
3	Correct	0 ms	440 KB	Output is correct
4	Correct	0 ms	348 KB	Output is correct
5	Correct	0 ms	348 KB	Output is correct
6	Correct	8 ms	2832 KB	Output is correct
7	Correct	20 ms	4836 KB	Output is correct
8	Correct	14 ms	4956 KB	Output is correct
9	Correct	5 ms	1864 KB	Output is correct
10	Correct	19 ms	5780 KB	Output is correct
11	Correct	0 ms	344 KB	Output is correct
12	Correct	0 ms	348 KB	Output is correct
13	Correct	11 ms	2552 KB	Output is correct
14	Correct	0 ms	348 KB	Output is correct
15	Correct	25 ms	5968 KB	Output is correct

Subtask #4
5.0 / 5.0

#	Verdict	Memory	Grader output
1	Correct	344 KB	Output is correct
2	Correct	344 KB	Output is correct
3	Correct	348 KB	Output is correct
4	Correct	348 KB	Output is correct
5	Correct	360 KB	Output is correct

Subtask #5
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	360 KB	Output is correct
2	Correct	0 ms	360 KB	Output is correct
3	Correct	0 ms	360 KB	Output is correct
4	Correct	1 ms	360 KB	Output is correct
5	Correct	0 ms	348 KB	Output is correct
6	Correct	0 ms	604 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	600 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	1 ms	344 KB	Output is correct
3	Correct	0 ms	348 KB	Output is correct
4	Correct	0 ms	348 KB	Output is correct
5	Correct	0 ms	440 KB	Output is correct
6	Correct	0 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	0 ms	348 KB	Output is correct
10	Correct	1 ms	612 KB	Output is correct
11	Correct	15 ms	5480 KB	Output is correct
12	Correct	18 ms	6248 KB	Output is correct
13	Correct	17 ms	4196 KB	Output is correct
14	Correct	17 ms	5432 KB	Output is correct
15	Correct	18 ms	3936 KB	Output is correct

Subtask #7
5.0 / 5.0

#	Verdict	Memory	Grader output
1	Correct	360 KB	Output is correct
2	Correct	360 KB	Output is correct
3	Correct	612 KB	Output is correct

Subtask #8
15.0 / 15.0

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

Subtask #9
15.0 / 15.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	0 ms	348 KB	Output is correct
4	Correct	0 ms	348 KB	Output is correct
5	Correct	0 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	0 ms	348 KB	Output is correct
9	Correct	27 ms	5724 KB	Output is correct
10	Correct	21 ms	4696 KB	Output is correct
11	Correct	8 ms	1992 KB	Output is correct
12	Correct	10 ms	2240 KB	Output is correct
13	Correct	2 ms	860 KB	Output is correct

Subtask #10
10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	600 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	0 ms	604 KB	Output is correct
4	Correct	0 ms	344 KB	Output is correct
5	Correct	0 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	0 ms	348 KB	Output is correct
9	Correct	26 ms	5724 KB	Output is correct
10	Correct	21 ms	4700 KB	Output is correct
11	Correct	11 ms	1996 KB	Output is correct
12	Correct	10 ms	2392 KB	Output is correct
13	Correct	2 ms	860 KB	Output is correct
14	Correct	33 ms	6648 KB	Output is correct
15	Correct	37 ms	7504 KB	Output is correct
16	Correct	6 ms	1628 KB	Output is correct
17	Correct	25 ms	5200 KB	Output is correct
18	Correct	13 ms	3164 KB	Output is correct

Submission #1063806

Compilation message