Submission #385879

#	Time	Username	Problem	Language	Result	Execution time	Memory
385879		Keshi	Gondola (IOI14_gondola)	C++17	75 / 100	60 ms	5100 KiB

gondola

//In the name of God
#include <bits/stdc++.h>
#include "gondola.h"
using namespace std;

typedef long long ll;
typedef pair<ll, ll> pll;

const ll maxn = 5e5 + 100;
const ll mod = 1e9 + 9;
const ll inf = 1e18;

#define fast_io ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define file_io freopen("input.txt", "r+", stdin);freopen("output.txt", "w+", stdout);
#define pb push_back
#define Mp make_pair
#define F first
#define S second
#define Sz(x) ll((x).size())
#define all(x) (x).begin(), (x).end()


int valid(int n, int inputSeq[]){
	map<int, int> vis;
	ll x = -1;
	for(ll i = 0; i < n; i++){
		if(vis[inputSeq[i]]) return 0;
		vis[inputSeq[i]] = 1;
		if(inputSeq[i] <= n) x = i;
	}
	if(x == -1) return 1;
	for(ll i = 0; i < n; i++){
		if(inputSeq[i] > n) continue;
		if((inputSeq[i] - inputSeq[x] + n) % n != (i - x + n) % n) return 0;
	}
	return 1;
}

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

int replacement(int n, int gondolaSeq[], int replacementSeq[]){
	ll a[n];
	ll x = 0;
	vector<pll> vec;
	for(ll i = 0; i < n; i++){
		if(gondolaSeq[i] <= n){
			x = (i - gondolaSeq[i] + n) % n;
		}
		else{
			vec.pb(Mp(gondolaSeq[i], i));
		}
	}
	sort(all(vec));
	for(ll i = 0; i < n; i++){
		a[i] = (-x + i + n) % n;
		if(a[i] == 0) a[i] = n;
	}
	ll p = n;
	ll t = 0;
	for(ll i = 0; i < Sz(vec); i++){
		while(p < vec[i].F){
			replacementSeq[t++] = a[vec[i].S];
			a[vec[i].S] = ++p;
		}
	}
	return t;
}

ll pw(ll a, ll b){
	ll c = 1;
	while(b){
		if(b & 1) c = c * a % mod;
		a = a * a % mod;
		b >>= 1;
	}
	return c;
}

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

int countReplacement(int n, int inputSeq[]){
	if(!valid(n, inputSeq)) return 0;
	vector<ll> vec;
	for(ll i = 0; i < n; i++){
		if(inputSeq[i] > n){
			vec.pb(inputSeq[i]);
		}
	}
	sort(all(vec));
	ll p = n;
	ll ans = 1;
	for(ll i = 0; i < Sz(vec); i++){
		ans = ans * pw(Sz(vec) - i, vec[i] - p - 1) % mod;
		p = vec[i];
	}
	return ans;
}

/*int main(){
    fast_io;



    return 0;
}*/

• 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: 0 / 15
• Subtask 10: 0 / 10