Submission #642078

#	Time	Username	Problem	Language	Result	Execution time	Memory
642078		QwertyPi	Gondola (IOI14_gondola)	C++14	100 / 100	67 ms	6140 KiB

gondola

#include <bits/stdc++.h>
using namespace std;

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

typedef long long ll;

void rotate(int n, int a[], int x){
	int b[n];
	for(int i = 0; i < n; i++){
		b[i] = a[(i + n - x) % n];
	}
	for(int i = 0; i < n; i++){
		a[i] = b[i];
	}
}

bool init(int n, int a[]){
	for(int i = 0; i < n; i++){
		if(a[i] <= n){
			rotate(n, a, a[i] - (i + 1));
			break;
		}
	}
	for(int i = 0; i < n; i++){
		if(a[i] <= n && a[i] != i + 1){
			return false;
		}
	}
	set<int> S;
	for(int i = 0; i < n; i++){
		S.insert(a[i]);
	}
	if(S.size() != n){
		return false;
	}
	return true;
}

int valid(int n, int a[]){
	return init(n, a);
}

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

int replacement(int n, int a[], int r[]){
	init(n, a);
	int l = 0;
	vector<int> seq;
	for(int i = 0; i < n; i++){
		seq.push_back(i + 1);
	}
	map<int, int> A; set<int> S;
	for(int i = 0; i < n; i++)
		A[a[i]] = i;
	for(int i = 0; i < n; i++){
		if(a[i] != i + 1){
			S.insert(i);
		}
	}
	int MAX_A = *max_element(a, a + n);
	for(int i = n + 1; i <= MAX_A; i++){
		if(!A.count(i)){
			r[l++] = seq[*S.begin()];
			seq[*S.begin()] = i;
		}else{
			r[l++] = seq[A[i]];
			seq[A[i]] = i;
			S.erase(A[i]);
		}
	}
	return l;
}

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

const ll MOD = 1e9 + 9;

ll bp(ll a, ll b){
	if(b == 0) return 1;
	return bp(a * a % MOD, b / 2) * (b % 2 ? a : 1) % MOD;
}

ll mi(ll a){
	return bp(a, MOD - 2);
}

ll C(ll n, ll r){
	ll ret = 1;
	for(ll i = n; i >= n - r + 1; i++){
		ret = (ret * i) % MOD;
	}
	for(ll i = 1; i <= r; i++){
		ret = (ret * mi(i)) % MOD;
	}
}

int countReplacement(int n, int a[]){
	bool ok = init(n, a);
	if(!ok) return 0;
	set<int> A; for(int i = 0; i < n; i++) A.insert(a[i]);
	int MAX_A = *--A.end(), MIN_A = *A.begin();
	ll FIXED = 0, _prev = n, ans = MIN_A > n ? n : 1;
	for(auto a : A){
		if(a > n){
			ans = ans * bp(n - FIXED, a - _prev - 1) % MOD;
			_prev = a;
		}
		FIXED++;
	}
	return ans;
}

#ifdef hkoi

int a[250001];
int b[250001];
int main() {
	int ST;
	cin >> ST;
	int n; cin >> n;
	for(int i = 0; i < n; i++)
		cin >> a[i];
	if(1 <= ST && ST <= 3){
		int ans = valid(n, a);
		cout << ans << '\n';
	}else if(4 <= ST && ST <= 6){
		int l = replacement(n, a, b);
		cout << l << '\n';
		for(int i = 0; i < l; i++){
			cout << b[i] << '\n';
		}
	}else if(7 <= ST && ST <= 10){
		int ans = countReplacement(n, a);
		cout << ans << '\n';
	}
}

#endif

Compilation message (stderr)

gondola.cpp: In function 'bool init(int, int*)':
gondola.cpp:36:14: warning: comparison of integer expressions of different signedness: 'std::set<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   36 |  if(S.size() != n){
      |     ~~~~~~~~~^~~~
gondola.cpp: In function 'll C(ll, ll)':
gondola.cpp:98:1: warning: no return statement in function returning non-void [-Wreturn-type]
   98 | }
      | ^
gondola.cpp: In function 'int countReplacement(int, int*)':
gondola.cpp:104:6: warning: unused variable 'MAX_A' [-Wunused-variable]
  104 |  int MAX_A = *--A.end(), MIN_A = *A.begin();
      |      ^~~~~

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