Submission #43780

#	Time	Username	Problem	Language	Result	Execution time	Memory
43780		faustaadp	Gondola (IOI14_gondola)	C++14	100 / 100	104 ms	18176 KiB

gondola

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

#define pb push_back
#define mp make_pair
#define fi first
#define se second

typedef pair<int, int> ip;
typedef long long ll;

int valid(int n, int inputSeq[])
{
	map<ll,bool> cek;
	int now = -1;
	for (int i = 0; i < n; i++) {
		if (cek[inputSeq[i]]) return 0;
		cek[inputSeq[i]] = true;
		if (inputSeq[i] <= n) {
			if (now == -1) now = inputSeq[i];
			else if (now != inputSeq[i]) return 0;
		}
		if (now != -1) now = (now%n)+1;
	}
	return 1;
}

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

int replacement(int n, int gondolaSeq[], int replacementSeq[])
{
	int arr[100010];
	for (int i = 0; i <= n; i++) {
		if (i == n) {
			for (int j = 0; j < n; j++) {
				arr[j] = j+1;
			}
			break;
		}
		if (gondolaSeq[i] <= n) {
			for (int j = 0; j < n; j++) {
				arr[j] = (gondolaSeq[i]+(j-i)+n)%n;
				if (arr[j] == 0) arr[j] = n;
			}
			break;
		}
	}
	vector <ip> v;
	v.clear();
	for (int i = 0; i < n; i++) {
		if (gondolaSeq[i] != arr[i]) {
			v.pb(mp(gondolaSeq[i], i));
		}
	}
	sort(v.begin(), v.end());
	int idx = 0;
	int maks;
	if (v.size() > 0) {
		maks = v[v.size()-1].fi;
	} else {
		return 0;
	}
	for (int x = n+1; x <= maks; x++) {
		int tmp = v[idx].se;
		replacementSeq[x-(n+1)] = arr[tmp];
//		cout << x << " " << tmp << " " << arr[tmp] << "\n";
		arr[tmp] = x;
		if (v[idx].fi == x) {
			idx++;
		}
	}
	return maks-n;
}

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

const ll MOD = 1e9+9;

ll pwr(ll x, ll p) {
	if (x == 0) return 0;
	if (x == 1) return 1;
	if (p == 1) return x;
	ll a = pwr((x*x)%MOD, p/2);
	if (p%2 == 1) return (a*x)%MOD;
	return a;
}

int countReplacement(int N, int Seq[])
{
	if (valid(N, Seq) == 0) {
		return 0;
	}
	ll n = N, inputSeq[100010];
	for (int i = 0; i < N; i++) inputSeq[i] = Seq[i];
	ll arr[100010];
	bool aman = false;
	for (ll i = 0; i <= n; i++) {
		if (i == n) {
			for (ll j = 0; j < n; j++) {
				arr[j] = j+1;
			}
			aman = true;
			break;
		}
		if (inputSeq[i] <= n) {
			for (ll j = 0; j < n; j++) {
				arr[j] = (inputSeq[i]+(j-i)+n)%n;
				if (arr[j] == 0) arr[j] = n;
			}
			break;
		}
	}
	vector <ll> v;
	v.pb(n);
	for (ll i = 0; i < n; i++) {
		if (inputSeq[i] > n) v.pb(inputSeq[i]);
	}
	sort(v.begin(), v.end());
	ll ct = 1, tot = v.size();
//	cout << tot << "  tot\n";
	for (ll i = 1; i < tot; i++) {
//		cout << i << ". " << v[i] << "\n";
		ll tmp = v[i]-v[i-1]-1ll;
		if (tmp == 0) continue;
		ct = (ct * pwr(tot-i, tmp))%MOD;
//		cout << i << " " << ct << " aaaa\n";
	}
	if (aman) ct = (ct*n)%MOD;
	return ct;
}

// BAWAH ADALAH GRADER ----------------------------------------------------------

//int gondolaSequence[100001];
//int replacementSequence[250001];
//
//int main()
//{
//  int i, n, tag;
//  int nr; 
//  assert(scanf("%d", &tag)==1);
//  assert(scanf("%d", &n)==1);
//  for(i=0;i< n;i++)
//    assert( scanf("%d", &gondolaSequence[i]) ==1);
//  
//  switch (tag){
//  case 1: case 2: case 3:
//    printf("%d\n", valid(n, gondolaSequence));
//    break;
//
//  case 4: case 5: case 6:
//    nr = replacement(n, gondolaSequence, replacementSequence);
//    printf("%d ", nr);
//    if (nr > 0)
//      {
//	for (i=0; i<nr-1; i++)
//	  printf("%d ", replacementSequence[i]);
//	printf("%d\n", replacementSequence[nr-1]);
//      }  
//    else printf("\n");
//    break;
//
//  case 7: case 8: case 9: case 10:
//    printf("%d\n",  countReplacement(n, gondolaSequence));  
//    break;
//  }
//
//  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: 15 / 15
• Subtask 10: 10 / 10