oj.uz

Submission #228611

# Submission time Handle Problem Language Result Execution time Memory
228611 2020-05-02T05:50:26 Z ryansee Gondola (IOI14_gondola) C++14
100 / 100
 49 ms 7304 KB 
#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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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