Submission #1061671

#	Time	Username	Problem	Language	Result	Execution time	Memory
1061671		Nonoze	Gondola (IOI14_gondola)	C++17	100 / 100	45 ms	6692 KiB

gondola

#include "gondola.h"
#include <bits/stdc++.h>
using namespace std;
#define sz(x) (int)(x).size()
#define all(x) (x).begin(), (x).end()
#define fi first
#define se second
#define pb push_back
#define mp make_pair

int valid(int n, int inputSeq[]) { vector<int> a;
	for (int i=0; i<n; i++) a.pb(inputSeq[i]);
	int first=-1;
	for (int i=0; i<n; i++) if (a[i]<=n) first=i;
	map<int, int> vec;
	int mx=0;
	for (auto &u: a) vec[u]++;
	for (auto u: vec) if (u.se>1) return 0;
	if (first==-1) return 0;
	rotate(a.begin(), a.begin()+(first-(a[first]-1)+n)%n, a.end());
	for (int i=0; i<n; i++) if (a[i]<=n && a[i]!=i+1) return 0;
	return 1;
}

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

int replacement(int n, int gondolaSeq[], int replacementSeq[]) { vector<int> a;
	for (int i=0; i<n; i++) a.pb(gondolaSeq[i]);
	int first=0;
	for (int i=0; i<n; i++) if (a[i]<=n) first=i;
	if (first) rotate(a.begin(), a.begin()+(first-(a[first]-1)+n)%n, a.end());
	map<int, int> vec;
	vector<int> ans;
	int mx=*max_element(all(a));
	for (int i=0; i<n; i++) vec[a[i]]=i, a[i]=i+1;
	for (int i=n+1; i<=mx; i++) {
		if (!vec.count(i)) ans.pb(a[vec.rbegin()->se]), a[vec.rbegin()->se]=i;
		else ans.pb(a[vec[i]]), a[vec[i]]=i;
	}

	for (int i=0; i<sz(ans); i++) replacementSeq[i]=ans[i];
	return sz(ans);
}

//----------------------
#define ll long long

const int MOD=1e9+9;

ll fastpow(int x, ll y) {
	if (y==0) return 1;
	ll temp=fastpow(x, y/2); temp=(temp*temp)%MOD;
	if (y%2) temp*=x;
	return temp%MOD;
}


int countReplacement(int n, int inputSeq[]) { vector<int> a;
	for (int i=0; i<n; i++) a.pb(inputSeq[i]);
	if (!valid(n, inputSeq) && *min_element(all(a))<=n) return 0;
	vector<int> vec(1, n);
	ll nxt=0, ans=1;
	for (int i=0; i<n; i++) if (a[i]>n) nxt++, vec.pb(a[i]);
	sort(all(vec));
	if (sz(vec)==n+1) ans=n;
	for (int i=0; i<sz(vec)-1; i++) {
		ans=(ans*fastpow(sz(vec)-i-1, vec[i+1]-vec[i]-1))%MOD;
	}
	return ans;
}

Compilation message (stderr)

gondola.cpp: In function 'int valid(int, int*)':
gondola.cpp:16:6: warning: unused variable 'mx' [-Wunused-variable]
   16 |  int mx=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: 15 / 15
• Subtask 10: 10 / 10