제출 #165380

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
165380		cfalas	곤돌라 (IOI14_gondola)	C++14	100 / 100	97 ms	8124 KiB

gondola

#include "gondola.h"
#include<bits/stdc++.h>
using namespace std;
#define MOD 1000000009
#define ll long long

int valid(int n, int a[]){
	map<int, bool> used;
	for(int i=0;i<n;i++){
		if(used[a[i]]) return 0;
		used[a[i]] = true;

	}
	int s = 0;
	for(int i=0;i<n;i++){
		if(a[i]<=n){
			s = i;
			break;
		}
	}

	for(int i=0;i<n;i++){
		if(a[i]<=n && (a[i]+(s-i) - 1 + n)%n + 1 != a[s]) return 0; }
	return 1;
}

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

int replacement(int n, int a[], int ans[]){
	int apos=-1, av;
	int maxf=0;
	int minf = 0;
	unordered_map<int, int> m;
	for(int i=0;i<n;i++){
		if(a[i]<=n) apos = i, av=a[i];
		else m[a[i]] = i+1;
		maxf = max(maxf, a[i]);
		if(a[minf]>a[i]) minf = i;
	}
	if(apos==-1){
		apos = minf;
		av = 1;
	}
	queue<int> q;
	int l=0;
	for(int i=n+1;i<=maxf;i++){
		if(m[i]){
			int c = l - 1;
			ans[l] = (n + av - (apos - m[i] + 1) - 1) % n + l - c;
			l++;
			//cout<<apos<<" "<<m[i]<<" "<<av<<endl;

			while(!q.empty()){
				ans[l] = q.front();
				q.pop();
				l++;
			}
		}
		else q.push(i);
	}
	return l;
}

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

ll mpow(ll a, ll b){
	if(b==0) return 1;
	if(b==1) return a;
	ll z = mpow(a, b/2);
	z*=z;
	z%=MOD;
	if(b%2) z*=a;
	z%=MOD;
	return z;
}

int countReplacement(int n, int a[]){
	if(!valid(n, a)) return 0;
	int act=-1;
	int un=0;
	for(int i=0;i<n;i++){
		if(a[i]<=n)	act = i;
		else un++;
	}
	sort(a, a+n);
	ll ans=1;
	if(act==-1) ans*=n;
	ll prev = n+1;
	for(int i=0;i<n-1 && un>=1;i++){
		if(a[i]<=n) continue;
		//cout<<un<<" "<<mpow(un, a[i+1]-a[i]-1)<<" "<<a[i]<<" "<<a[i+1]<<endl;
		ans *= mpow(un, a[i]-prev);
		ans%=MOD;
		prev = a[i]+1;
		un--;
	}
	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: 10 / 10