Submission #1153879

#	Time	Username	Problem	Language	Result	Execution time	Memory
1153879		zhasyn	곤돌라 (IOI14_gondola)	C++20	90 / 100	12 ms	2364 KiB

gondola

#include "gondola.h"
#include <bits/stdc++.h>
#define pb push_back
#define pf push_front
using namespace std;
#define F first
#define S second
typedef long long ll;
#define pii pair <int, int>
#define pll pair <ll, ll>
typedef long double ld;
const ll N = 3 * 1e5 + 100, M = 1e7 + 10, len = 21, inf = 1e18;
const ll mod = 1000000009LL;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
ll um(ll a, ll b){
	return (1LL * a * b) % mod;
}
ll subr(ll a, ll b){
	return ((1LL * a - b) % mod + mod) % mod;
}
bool cc[N];
int valid(int n, int arr[])
{
  int cur = 0;
  bool was = false;
  for(int i = 0; i < 2 * n; i++){
  	cur = cur%n + 1;
  	if(i < n){
	  	if(cc[arr[i%n]] == true) return 0;
	  	cc[arr[i%n]] = true;
  	}
  	if(was){
  		if(arr[i%n] > n) continue;
  		if(arr[i%n] != cur) return 0;
  	} else{
  		if(arr[i%n] <= n){
  			was = true;
  			cur = arr[i%n];
  		}
  	}
  }
  return 1;
}

//----------------------
int replacement(int n, int arr[], int res[])
{
  int cur = 0;
  bool was = false;
  vector <pii> vec;
  for(int i = 0; i < 2 * n; i++){
  	cur = cur%n + 1;
  	if(was == false && arr[i%n] <= n){
  		was = true;
  		cur = arr[i%n];
  	}
  	if(was == true){
  		if(cc[cur]) continue;
  		cc[cur] = true;
  		vec.pb({arr[i%n], cur});
  	}
  }
  if(was == false){
  	for(int i = 0; i < n; i++){
  		vec.pb({arr[i], i + 1});
  	}
  }
  sort(vec.begin(), vec.end());
  int from = 0, lt;
  bool mk = false;
  for(int i = 0; i < (int)vec.size(); i++){
  	if(vec[i].F == vec[i].S) continue;
  	res[from++] = vec[i].S;
  	if(mk == false) lt = n + 1;
  	else lt = vec[i - 1].F + 1;
  	for(int j = lt; j < vec[i].F; j++){
  		res[from++] = j;
  	}
  	mk = true;
  }
  return from;
}

//----------------------
ll binpow(ll x, ll step){
	ll res = 1;
	while(step){
		if(step & 1) res = um(res, x);
		x = um(x, x);
		step /= 2;
	}
	return res;
}
int countReplacement(int n, int arr[])
{
	int rs = valid(n, arr);
	if(rs == 0) return 0;
	
  int cur = 0, mx = 0;
  ll ans = 1, cnt = 0;
  bool was = false;
  vector <pii> vec;
  for(int i = 0; i < 2 * n; i++){
  	cur = cur%n + 1;
  	mx = max(mx, arr[i % n]);
  	if(was == false && arr[i%n] <= n){
  		was = true;
  		cur = arr[i%n];
  	}
  	if(was == true){
  		if(cc[cur]) continue;
  		cc[cur] = true;
  		vec.pb({arr[i%n], cur});
  	}
  }
  if(was == false){
  	for(int i = 0; i < n; i++){
  		vec.pb({arr[i], i + 1});
  	}
  	ans = n;
  }
  sort(vec.begin(), vec.end());
  for(int i = 0; i < (int)vec.size(); i++){
  	if(vec[i].F == vec[i].S) continue;
  	cnt++;
  }
  ll last = n;
  for(int i = 0; i < (int)vec.size(); i++){
  	if(vec[i].F == vec[i].S) continue;
  	ans = um(ans, binpow(cnt, vec[i].F - last - 1));
  	cnt--;
  	last = vec[i].F;
  }
  return ans;
}

• Subtask 1: 5 / 5
• Subtask 2: 5 / 5
• Subtask 3: 10 / 10
• Subtask 4: 5 / 5
• Subtask 5: 10 / 10
• Subtask 6: 20 / 20
• Subtask 7: 5 / 5
• Subtask 8: 15 / 15
• Subtask 9: 15 / 15
• Subtask 10: 0 / 10