답안 #228611

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
228611	2020-05-02T05:50:26 Z	ryansee	곤돌라 (IOI14_gondola)	C++14	100 / 100	49 ms	7304 KB

gondola

#include "gondola.h"

#include "bits/stdc++.h"
using namespace std;

#define FAST ios_base::sync_with_stdio(false); cin.tie(0);
#define pb push_back
#define eb emplace_back
#define ins insert
#define f first
#define s second
#define cbr cerr << "hi\n"
#define mmst(x, v) memset((x), v, sizeof ((x)))
#define siz(x) ll(x.size())
#define all(x) (x).begin(), (x).end()
#define lbd(x,y) (lower_bound(all(x),y)-x.begin())
#define ubd(x,y) (upper_bound(all(x),y)-x.begin())
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());    //can be used by calling rng() or shuffle(A, A+n, rng)
inline long long rand(long long x, long long y) { return (rng() % (y+1-x)) + x; } //inclusivesss
string inline to_string(char c) {string s(1,c);return s;} template<typename T> inline T gcd(T a,T b){ return a==0?llabs(b):gcd(b%a,a); }

typedef long long ll; 
typedef long double ld;
#define FOR(i,s,e) for(ll i=s;i<=ll(e);++i)
#define DEC(i,s,e) for(ll i=s;i>=ll(e);--i)
typedef pair<ll,ll>pi; typedef pair<ll,pi>spi; typedef pair<pi,pi>dpi;

#define LLINF ((long long)1e18)
#define INF int(1e9+1e6)
#define MAXN (100006)
ll n;
unordered_map<ll,ll>exists,pos;
int valid(int N, int A[]) {
	n=N;
	ll shift=-1;
	FOR(i,0,n-1)--A[i];
	FOR(i,0,n-1)if(exists[A[i]])return 0;else exists[A[i]]=1;
	FOR(i,0,n-1)if(A[i]<n){
		if(~shift){if((i+shift)%n!=A[i])return 0;}
		else shift=(A[i]-i+n)%n;
	}
	return 1;
}
void shifty(int*A){
	ll shift=0;
	FOR(i,0,n-1)if(A[i]<=n)shift=(A[i]-1-i+n)%n;
	vector<ll> B(n);
	FOR(i,0,n-1)B[(i+shift)%n]=A[i];
	FOR(i,0,n-1)A[i]=B[i];
}
int replacement(int N, int A[], int B[]) {
	n=N;
	shifty(A);
	ll mx=max_element(A,A+n)-A;
	FOR(i,0,n-1)pos[A[i]]=i;
	ll co=0,val=mx+1;
	FOR(i,n+1,A[mx]){
		if(pos.count(i) && i!=A[mx]) B[co++]=pos[i]+1;
		else B[co++]=val, val=i;
	}
	return co;
}
ll mod=1e9+9;
int B[MAXN];
int countReplacement(int N, int A[]) {
	n=N;
	FOR(i,0,n-1)B[i]=A[i];
	ll ans=valid(n,B);
	vector<ll> hmm;
	FOR(i,0,n-1)if(A[i]>n)hmm.eb(A[i]);
	sort(all(hmm));
	auto qexp=[&](ll x,ll e){
		ll sum=1;
		while(e){
			if(e&1)sum*=x,sum%=mod;
			x*=x,x%=mod;
			e>>=1;
		}
		return sum;
	};
	// assert(siz(hmm)<n);
	FOR(i,0,siz(hmm)-1){
		if(hmm[i]-1-(i?hmm[i-1]:n) > 0) {
		    ll p=hmm[i]-1-(i?hmm[i-1]:n);
			ans *= qexp(siz(hmm) - i, p), ans %= mod;
		}
	}
	if(siz(hmm)==n) ans*=n, ans%=mod;
	return ans;
}

Subtask #1
5.0 / 5.0

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

Subtask #2
5.0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Correct	5 ms	416 KB	Output is correct
2	Correct	5 ms	384 KB	Output is correct
3	Correct	4 ms	384 KB	Output is correct
4	Correct	5 ms	384 KB	Output is correct
5	Correct	4 ms	384 KB	Output is correct
6	Correct	14 ms	2224 KB	Output is correct
7	Correct	18 ms	1280 KB	Output is correct
8	Correct	22 ms	4112 KB	Output is correct
9	Correct	11 ms	1536 KB	Output is correct
10	Correct	24 ms	4624 KB	Output is correct

Subtask #3
10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	5 ms	384 KB	Output is correct
2	Correct	5 ms	384 KB	Output is correct
3	Correct	5 ms	384 KB	Output is correct
4	Correct	4 ms	384 KB	Output is correct
5	Correct	5 ms	384 KB	Output is correct
6	Correct	13 ms	2352 KB	Output is correct
7	Correct	17 ms	1280 KB	Output is correct
8	Correct	23 ms	4112 KB	Output is correct
9	Correct	10 ms	1536 KB	Output is correct
10	Correct	25 ms	4624 KB	Output is correct
11	Correct	5 ms	384 KB	Output is correct
12	Correct	5 ms	384 KB	Output is correct
13	Correct	16 ms	2224 KB	Output is correct
14	Correct	5 ms	384 KB	Output is correct
15	Correct	31 ms	4752 KB	Output is correct

Subtask #4
5.0 / 5.0

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

Subtask #5
10.0 / 10.0

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

Subtask #6
20.0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	5 ms	384 KB	Output is correct
2	Correct	5 ms	384 KB	Output is correct
3	Correct	4 ms	384 KB	Output is correct
4	Correct	5 ms	384 KB	Output is correct
5	Correct	5 ms	384 KB	Output is correct
6	Correct	5 ms	384 KB	Output is correct
7	Correct	5 ms	384 KB	Output is correct
8	Correct	6 ms	384 KB	Output is correct
9	Correct	5 ms	384 KB	Output is correct
10	Correct	6 ms	384 KB	Output is correct
11	Correct	23 ms	4500 KB	Output is correct
12	Correct	26 ms	4928 KB	Output is correct
13	Correct	24 ms	2928 KB	Output is correct
14	Correct	24 ms	4372 KB	Output is correct
15	Correct	31 ms	3068 KB	Output is correct

Subtask #7
5.0 / 5.0

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

Subtask #8
15.0 / 15.0

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

Subtask #9
15.0 / 15.0

#	결과	실행 시간	메모리	Grader output
1	Correct	5 ms	384 KB	Output is correct
2	Correct	5 ms	384 KB	Output is correct
3	Correct	5 ms	384 KB	Output is correct
4	Correct	5 ms	384 KB	Output is correct
5	Correct	5 ms	384 KB	Output is correct
6	Correct	5 ms	384 KB	Output is correct
7	Correct	5 ms	384 KB	Output is correct
8	Correct	5 ms	384 KB	Output is correct
9	Correct	35 ms	5656 KB	Output is correct
10	Correct	29 ms	4880 KB	Output is correct
11	Correct	13 ms	1920 KB	Output is correct
12	Correct	16 ms	2480 KB	Output is correct
13	Correct	7 ms	896 KB	Output is correct

Subtask #10
10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	4 ms	384 KB	Output is correct
2	Correct	5 ms	384 KB	Output is correct
3	Correct	5 ms	384 KB	Output is correct
4	Correct	6 ms	384 KB	Output is correct
5	Correct	5 ms	384 KB	Output is correct
6	Correct	5 ms	384 KB	Output is correct
7	Correct	5 ms	384 KB	Output is correct
8	Correct	4 ms	384 KB	Output is correct
9	Correct	34 ms	5520 KB	Output is correct
10	Correct	33 ms	4872 KB	Output is correct
11	Correct	14 ms	1920 KB	Output is correct
12	Correct	16 ms	2480 KB	Output is correct
13	Correct	7 ms	896 KB	Output is correct
14	Correct	45 ms	6792 KB	Output is correct
15	Correct	49 ms	7304 KB	Output is correct
16	Correct	13 ms	1792 KB	Output is correct
17	Correct	38 ms	5256 KB	Output is correct
18	Correct	21 ms	3248 KB	Output is correct

답안 #228611

Compilation message