답안 #378321

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
378321	2021-03-16T13:21:18 Z	AmineWeslati	곤돌라 (IOI14_gondola)	C++14	100 / 100	36 ms	3172 KB

gondola

//Never stop trying
#include "bits/stdc++.h"
using namespace std;
#define boost ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0)

typedef long long ll;
typedef string str;
typedef long double ld;
typedef pair<int, int> pi;
#define fi first
#define se second
typedef vector<int> vi;
typedef vector<pi> vpi;
#define pb push_back
#define eb emplace_back
#define sz(x) (int)x.size()
#define all(x) begin(x), end(x)
#define rall(x) rbegin(x), rend(x)
#define endl "\n"
#define FOR(i,a,b) for (int i = (a); i < (b); ++i)
#define ROF(i,a,b) for (int i = (b)-1; i >= (a); --i)

const ll MOD = 1e9 + 9; //998244353
const ll INF = 1e9;
const int MX = 2e5 + 10;
const int nx[4] = {0, 0, 1, -1}, ny[4] = {1, -1, 0, 0}; //right left down up

template<class T> using V = vector<T>;
template<class T> bool ckmin(T& a, const T& b) { return a > b ? a = b, 1 : 0; }
template<class T> bool ckmax(T& a, const T& b) { return a < b ? a = b, 1 : 0; }
ll cdiv(ll a, ll b) { return a / b + ((a ^ b) > 0 && a % b); } // divide a by b rounded up
//constexpr int log2(int x) { return 31 - __builtin_clz(x); } // floor(log2(x))

mt19937 rng(chrono::system_clock::now().time_since_epoch().count());
//mt19937_64 rng(chrono::system_clock::now().time_since_epoch().count());
ll random(ll a, ll b){
    return a + rng() % (b - a + 1);
}
#ifndef LOCAL  
#define cerr if(false) cerr
#endif
#define dbg(x) cerr << #x << " : " << x << endl; 
#define dbgs(x,y) cerr << #x << " : " << x << " / " << #y << " : " << y << endl;
#define dbgv(v) cerr << #v << " : " << "[ "; for(auto it : v) cerr << it << ' '; cerr << ']' << endl;
#define here() cerr << "here" << endl;

void IO() {
#ifdef LOCAL
    freopen("input.txt", "r", stdin); 
    freopen("output.txt", "w", stdout);
#endif
}
/////////////////////////ONLY CLEAN CODES ALLOWED/////////////////////////

#ifndef LOCAL
#include "gondola.h"
#endif

int valid(int N, int b[]){
	int a[N]; FOR(i,0,N) a[i]=b[i];

	deque<pi> vec;
	int st=INF;
	FOR(i,0,N) if(a[i]<=N){
		vec.eb(a[i],i);
		ckmin(st,a[i]);
	}
	sort(a,a+N);
	FOR(i,1,N) if(a[i]==a[i-1]) return 0;


	while(sz(vec) && vec[0].fi>st){
		vec.eb(vec[0].fi,vec[0].se+N);
		vec.pop_front();
	}

	FOR(i,1,sz(vec)){
		if(vec[i].fi<=vec[i-1].fi) return 0;
		if(vec[i].fi-vec[i-1].fi!=vec[i].se-vec[i-1].se) return 0;
	}

	return 1;

}

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

int replacement(int N, int a[], int ans[]){
	vpi vec;
	FOR(i,0,N) if(a[i]>N) vec.eb(a[i],i);
	sort(all(vec));

	if(sz(vec)==N){
		FOR(i,0,N) a[i]=i+1;
	}
	else{
		FOR(i,0,N) if(a[i]<=N){
			FOR(j,i+1,N) a[j]=a[j-1]+1;
			ROF(j,0,i) a[j]=a[j+1]-1;
			break;
		}
		FOR(i,0,N){
			if(a[i]<=0) a[i]+=N;
			else if(a[i]>N) a[i]-=N;
		}
	}

	int p=N,cnt=0;
	for(auto it: vec){
		int x=it.fi,idx=it.se;
		FOR(j,0,x-p){
			ans[cnt++]=a[idx];
			a[idx]=N+cnt;
		}
		p=x;
	}
	return cnt;
}

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

ll modpow(int x, int p){
	if(!p) return 1;
	ll v=modpow(x,p/2);
	v*=v; v%=MOD;
	if(p&1) v*=x,v%=MOD;
	return v;
}

ll f(int n){
	ll ans=1;
	FOR(i,1,n+1) ans*=i,ans%=MOD;
	return ans;
}

int countReplacement(int N, int a[]){
	if(!valid(N,a)) return 0;

	vpi vec;
	FOR(i,0,N) if(a[i]>N) vec.eb(a[i],i);
	sort(all(vec));

	int p=N; ll ans=1;
	FOR(i,0,sz(vec)){
		int x=vec[i].fi;
		assert(p!=x);

		ans*=modpow(sz(vec)-i,x-p-1); 
		ans%=MOD;

		p=x;
	}
	if(sz(vec)==N) ans*=N,ans%=MOD;
	return ans;
	
}

#ifdef LOCAL
int main() {
    boost; IO();

    int N; cin>>N;
    int a[N],ans[N*10];
    FOR(i,0,N) cin>>a[i];
    //cout << valid(N,a) << endl;
    cout << countReplacement(N,a) << endl;
    

    return 0;
}
#endif
//Change your approach

Subtask #1
5.0 / 5.0

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

Subtask #2
5.0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	364 KB	Output is correct
2	Correct	1 ms	364 KB	Output is correct
3	Correct	1 ms	364 KB	Output is correct
4	Correct	1 ms	364 KB	Output is correct
5	Correct	1 ms	364 KB	Output is correct
6	Correct	8 ms	876 KB	Output is correct
7	Correct	17 ms	1772 KB	Output is correct
8	Correct	13 ms	1516 KB	Output is correct
9	Correct	6 ms	876 KB	Output is correct
10	Correct	19 ms	1644 KB	Output is correct

Subtask #3
10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	364 KB	Output is correct
2	Correct	1 ms	364 KB	Output is correct
3	Correct	1 ms	364 KB	Output is correct
4	Correct	1 ms	364 KB	Output is correct
5	Correct	1 ms	364 KB	Output is correct
6	Correct	8 ms	876 KB	Output is correct
7	Correct	18 ms	1772 KB	Output is correct
8	Correct	13 ms	1516 KB	Output is correct
9	Correct	5 ms	748 KB	Output is correct
10	Correct	19 ms	1716 KB	Output is correct
11	Correct	1 ms	364 KB	Output is correct
12	Correct	1 ms	364 KB	Output is correct
13	Correct	9 ms	620 KB	Output is correct
14	Correct	1 ms	364 KB	Output is correct
15	Correct	19 ms	1516 KB	Output is correct

Subtask #4
5.0 / 5.0

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

Subtask #5
10.0 / 10.0

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

Subtask #6
20.0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	364 KB	Output is correct
2	Correct	1 ms	364 KB	Output is correct
3	Correct	1 ms	364 KB	Output is correct
4	Correct	1 ms	364 KB	Output is correct
5	Correct	1 ms	364 KB	Output is correct
6	Correct	1 ms	364 KB	Output is correct
7	Correct	1 ms	364 KB	Output is correct
8	Correct	1 ms	364 KB	Output is correct
9	Correct	1 ms	364 KB	Output is correct
10	Correct	1 ms	364 KB	Output is correct
11	Correct	10 ms	620 KB	Output is correct
12	Correct	12 ms	620 KB	Output is correct
13	Correct	19 ms	1276 KB	Output is correct
14	Correct	11 ms	620 KB	Output is correct
15	Correct	30 ms	2276 KB	Output is correct

Subtask #7
5.0 / 5.0

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

Subtask #8
15.0 / 15.0

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

Subtask #9
15.0 / 15.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	364 KB	Output is correct
2	Correct	0 ms	364 KB	Output is correct
3	Correct	1 ms	364 KB	Output is correct
4	Correct	1 ms	364 KB	Output is correct
5	Correct	1 ms	364 KB	Output is correct
6	Correct	1 ms	364 KB	Output is correct
7	Correct	0 ms	364 KB	Output is correct
8	Correct	0 ms	364 KB	Output is correct
9	Correct	23 ms	1512 KB	Output is correct
10	Correct	18 ms	1512 KB	Output is correct
11	Correct	7 ms	876 KB	Output is correct
12	Correct	10 ms	876 KB	Output is correct
13	Correct	4 ms	492 KB	Output is correct

Subtask #10
10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	364 KB	Output is correct
2	Correct	1 ms	364 KB	Output is correct
3	Correct	1 ms	364 KB	Output is correct
4	Correct	1 ms	364 KB	Output is correct
5	Correct	1 ms	492 KB	Output is correct
6	Correct	1 ms	364 KB	Output is correct
7	Correct	1 ms	364 KB	Output is correct
8	Correct	1 ms	364 KB	Output is correct
9	Correct	22 ms	1512 KB	Output is correct
10	Correct	18 ms	1640 KB	Output is correct
11	Correct	7 ms	876 KB	Output is correct
12	Correct	9 ms	876 KB	Output is correct
13	Correct	2 ms	492 KB	Output is correct
14	Correct	36 ms	2916 KB	Output is correct
15	Correct	34 ms	3172 KB	Output is correct
16	Correct	6 ms	1004 KB	Output is correct
17	Correct	26 ms	2152 KB	Output is correct
18	Correct	13 ms	1660 KB	Output is correct

답안 #378321

Compilation message