제출 #739341

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
739341		NeroZein	Gondola (IOI14_gondola)	C++17	70 / 100	18 ms	2732 KiB

gondola

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

const int N = (int) 1e5 + 1; 
const int M = (int) 1e9 + 1;
const int md = (int) 1e9 + 9; 

inline int binPow(int a, long long p){
	int res = 1;
	while (p){
		if (p & 1) res = (long long) res * a % md;
		a = (long long) a * a % md;
		p >>= 1LL;
	}
	return res;
}

int n; 
int mx; 
int a[N]; 
int b[N]; 
bitset<M> vis;

bool Go (int id, int cur, int step) {
	if (id < 0 || id >= n) {
		return true; 
	}
	if (cur == 0) cur = n; 
	if (cur == n + 1) cur = 1; 
	b[id] = cur; 
	if (a[id] <= n && a[id] != cur) {
		return false; 
	}
	return Go(id + step, cur + step, step); 
}; 
 
int valid(int n_, int inputSeq[]) {
	n = n_; 
	for (int i = 0; i < n; ++i) {
		a[i] = inputSeq[i]; 
	}
	for (int i = 0; i < n; ++i) {
		if (vis[a[i]] == true) {
			return false; 
		}
		mx = max(mx, a[i]);
		vis[a[i]] = true;
	}
	bool ret = true; 
  for (int i = 0; i < n; ++i) {
		if (inputSeq[i] <= n) {
			ret &= Go(i, a[i], 1);
			vis[inputSeq[i]] = 0;  
			ret &= Go(i, a[i], -1); 
			break; 
		}
	}
	return ret;
}
 
int replacement(int n_, int gondolaSeq[], int replacementSeq[]) {
	n = n_; 
	for (int i = 0; i < n; ++i) {
		a[i] = gondolaSeq[i]; 
	}
	bool f = false; 
	for (int i = 0; i < n; ++i) {
		mx = max(mx, a[i]); 
		vis[a[i]] = true; 
		if (a[i] <= n) {
			f = true; 
		}
	}
	int ans = 0; 
	if (!f) {
		for (int i = 1; i <= mx; ++i) {
			if (!vis[i]) {
				replacementSeq[ans++] = i;  
			}
		}
		return ans; 		
	}
	for (int i = 0; i < n; ++i) {
		if (a[i] <= n) {
			Go(i, a[i], 1); 
			Go(i, a[i], -1); 
			break; 
		}
	}
	vector<pair<int, int>> ord;
	for (int i = 0; i < n; ++i) {
		if (a[i] > n) {
			ord.push_back(make_pair(a[i], b[i])); 			
		}
	} 
	sort(ord.begin(), ord.end()); 
	for (int p = 0, g = n + 1; p < (int) ord.size(); ++p) {
		replacementSeq[ans++] = ord[p].second; 
		while (g < ord[p].first) {
			replacementSeq[ans++] = g++;		
		}
		g++; 
	}
	return ans; 
}
 
//----------------------
 
int countReplacement(int n_, int inputSeq[]) {
	n = n_; 
  if (!valid(n, inputSeq)) {
		return 0; 
	}
	bool f = false; 
	for (int i = 0; i < n; ++i) {
		a[i] = inputSeq[i]; 
		if (inputSeq[i] <= n) {
			f = true; 
		}
	}
	int ans = 1;
	if (!f) {
		ans = n; 
	}
	vector<int> v; 
	for (int i = 0; i < n; ++i) {
		v.push_back(a[i]); 
	}
	if (!vis[n]) {
		v.push_back(n); 		
	}
	sort(v.begin(), v.end());
	reverse(v.begin(), v.end());
	for (int i = 0; i < (int) v.size(); ++i) {
		if (v[i] <= n) {
			break; 
		}
		int cnt = v[i] - v[i + 1] - 1; 
		int p = i + 1; 
		ans = (long long) ans * binPow(p, cnt) % md; 
	}
	return ans; 
}

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