oj.uz

Submission #332518

# Submission time Handle Problem Language Result Execution time Memory
332518 2020-12-02T18:27:13 Z CSQ31 Gondola (IOI14_gondola) C++14
100 / 100
 145 ms 13192 KB 
#pragma GCC optimize("Ofast") 
#include "gondola.h"
#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define fi first
#define se second
#define sz(a) (int)a.size()
#define all(a) a.begin(),a.end()
#define lb lower_bound
#define ub upper_bound
#define owo ios_base::sync_with_stdio(0);cin.tie(0);
#define MOD (ll)(1e9+9)
#define INF (ll)(1e18)
#define debug(...) fprintf(stderr, __VA_ARGS__),fflush(stderr)
#define time__(d) for(long blockTime = 0; (blockTime == 0 ? (blockTime=clock()) != 0 : false);\
debug("%s time : %.4fs\n", d, (double)(clock() - blockTime) / CLOCKS_PER_SEC))
typedef long long int ll;
typedef long double ld;
typedef pair<ll,ll> PII;
typedef pair<int,int> pii;
typedef vector<vector<int>> vii;
typedef vector<vector<ll>> VII;
ll gcd(ll a,ll b){if(!b)return a;else return gcd(b,a%b);}
ll binpow(ll n,ll k){
	ll res = 1;
	while(k){
		if(k&1)res*=n;
		res%=MOD;
		n*=n;
		n%=MOD;
		k/=2;
	}
	return res;
}
int valid(int n, int inputSeq[])
{
	
	  vector<int>a(n);
	  for(int i=0;i<n;i++)a[i] = inputSeq[i];
	  int mn=1e9,id=0,mx = 0;
	  bool ok = 1;
	  map<int,bool>seen;
	  vector<pii>pos;
	  for(int i=0;i<n;i++){
		  if(a[i] < mn){
			  mn = a[i];
			  id = i;
		  }
		  if(seen[a[i]])ok = 0;
		  seen[a[i]] = 1;
		  mx = max(mx,a[i]);
	  }
	  vector<int>b;
	  for(int i=0;i<n;i++){
		  b.pb(a[(id+i)%n]);
	  }
	  for(int i=0;i<n;i++){
		  if(b[i]<=n)pos.pb({b[i],i});
	  }
	 // for(auto x:pos)cout<<x.fi<<" "<<x.se<<'\n';
	  if(mx == n){
	    sort(all(a));
	    if(a != b)ok = 0;
	  }else{
		  mx = 0;
		  for(int i=0;i<sz(pos);i++){
			   if(i && pos[i].se - pos[i-1].se != pos[i].fi - pos[i-1].fi)ok = 0;
		  }
		  
	  }
	  return ok;
}


int replacement(int n, int gondolaSeq[], int replacementSeq[])
{
	vector<int>a(n);
	for(int i=0;i<n;i++)a[i] = gondolaSeq[i];
	map<int,bool>seen;
	int mx = 0;
	for(int i=0;i<n;i++){
		seen[a[i]] = 1;
		mx = max(mx,a[i]);
	}
	int ans = 0;
	bool fix = 0;
	for(int i=1;i<=n;i++)if(seen[i])fix = 1;
	if(fix){
		vector<int>b(n);
		int sh = 0;
		for(int i=0;i<n;i++){
			if(a[i] <= n){
				sh = i - (a[i]-1);
				break;
			}
		}
		for(int i=0;i<n;i++)b[i] = a[(i+sh+n)%n];
		for(int i=0;i<n;i++)a[i] = b[i];
	}
	vector<pii>pos;
	for(int i=0;i<n;i++){
		if(a[i] > n)pos.pb({a[i],i+1});
	}
	sort(all(pos),greater<pii>());

	vector<int>opt;
	for(int i=0;i<sz(pos);i++){
		int num;
		if(i != sz(pos)-1)num = pos[i].fi-pos[i+1].fi;
		else num = pos[i].fi - n;
		ans+=num;
		while(num--){
			opt.pb(pos[i].se);
		}
	}
	reverse(all(opt));
	vector<int>c(n+1);
	for(int i=1;i<=n;i++)c[i] = i;
	int cnt = n;
	int i = 0;
	for(int x:opt){
		replacementSeq[i] = c[x];
		i++;
		c[x] = ++cnt;
	}
	return ans;
		
}

int countReplacement(int n, int inputSeq[])
{
	if(!valid(n,inputSeq))return 0;
	vector<int>a(n);
	for(int i=0;i<n;i++)a[i] = inputSeq[i];
	map<int,bool>seen;
	int mx = 0;
	for(int i=0;i<n;i++){
		seen[a[i]] = 1;
		mx = max(mx,a[i]);
	}
	bool fix = 0;
	for(int i=1;i<=n;i++)if(seen[i])fix = 1;
	if(fix){
		vector<int>b(n);
		int sh = 0;
		for(int i=0;i<n;i++){
			if(a[i] <= n){
				sh = i - (a[i]-1);
				break;
			}
		}
		for(int i=0;i<n;i++)b[i] = a[(i+sh+n)%n];
		for(int i=0;i<n;i++)a[i] = b[i];
	}
	vector<pii>pos;
	for(int i=0;i<n;i++){
		if(a[i] > n)pos.pb({a[i],i+1});
	}
	sort(all(pos),greater<pii>());
    /*
	vector<int>opt;
	for(int i=0;i<sz(pos);i++){
		int num;
		if(i != sz(pos)-1)num = pos[i].fi-pos[i+1].fi;
		else num = pos[i].fi - n;
		while(num--){
			opt.pb(pos[i].se);
		}
	}	
	map<int,bool>diff;
	for(int x:opt)diff[x] = 1;
	int s = sz(diff); //there are only s fix points in opt
	//the rest we can just go wild;
	int ans = 1;
	for(int i=0;i<sz(opt)-s;i++){
		ans = (ans*s)%MOD;
	}*/
	//wrong sol after each fix point,candidates decrease by one
	vector<ll>s;
	for(int i=0;i<n;i++){
		if(a[i] > n)s.pb(a[i]);
	}
	sort(all(s));
	ll ans = 1;
	ll cur = n+1;
	ll cnt = sz(s);
	for(int x:s){
		ans = (ans*binpow(cnt,x-cur))%MOD;
		cnt--;
		cur = x+1;
	}
	if(!fix)ans = (ans*n)%MOD;
	return ans;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory 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 0 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory 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 0 ms 364 KB Output is correct
5 Correct 0 ms 364 KB Output is correct
6 Correct 19 ms 3176 KB Output is correct
7 Correct 43 ms 5480 KB Output is correct
8 Correct 36 ms 5736 KB Output is correct
9 Correct 11 ms 2028 KB Output is correct
10 Correct 43 ms 6376 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory 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
6 Correct 19 ms 3176 KB Output is correct
7 Correct 45 ms 5608 KB Output is correct
8 Correct 36 ms 5736 KB Output is correct
9 Correct 11 ms 2028 KB Output is correct
10 Correct 43 ms 6524 KB Output is correct
11 Correct 0 ms 364 KB Output is correct
12 Correct 1 ms 376 KB Output is correct
13 Correct 20 ms 2668 KB Output is correct
14 Correct 1 ms 364 KB Output is correct
15 Correct 54 ms 6120 KB Output is correct

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory 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 0 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory 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 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 492 KB Output is correct

Subtask #6
20.0 / 20.0

# Verdict Execution time Memory 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 492 KB Output is correct
11 Correct 35 ms 4972 KB Output is correct
12 Correct 40 ms 5792 KB Output is correct
13 Correct 34 ms 4584 KB Output is correct
14 Correct 43 ms 4972 KB Output is correct
15 Correct 34 ms 3928 KB Output is correct

Subtask #7
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 384 KB Output is correct

Subtask #8
15.0 / 15.0

# Verdict Execution time Memory 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 0 ms 364 KB Output is correct
8 Correct 1 ms 364 KB Output is correct

Subtask #9
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 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 384 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 1 ms 364 KB Output is correct
9 Correct 93 ms 8996 KB Output is correct
10 Correct 72 ms 7164 KB Output is correct
11 Correct 27 ms 3348 KB Output is correct
12 Correct 33 ms 3840 KB Output is correct
13 Correct 7 ms 1260 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory 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 0 ms 364 KB Output is correct
7 Correct 0 ms 364 KB Output is correct
8 Correct 1 ms 364 KB Output is correct
9 Correct 93 ms 8996 KB Output is correct
10 Correct 76 ms 7164 KB Output is correct
11 Correct 26 ms 3348 KB Output is correct
12 Correct 33 ms 3840 KB Output is correct
13 Correct 7 ms 1260 KB Output is correct
14 Correct 123 ms 11992 KB Output is correct
15 Correct 145 ms 13192 KB Output is correct
16 Correct 22 ms 2852 KB Output is correct
17 Correct 87 ms 8692 KB Output is correct
18 Correct 47 ms 5464 KB Output is correct