답안 #43780 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
43780	2018-03-23T15:56:07 Z	faustaadp	곤돌라 (IOI14_gondola)	C++14	100 / 100	104 ms	18176 KB

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.0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	248 KB	Output is correct
2	Correct	2 ms	356 KB	Output is correct
3	Correct	2 ms	464 KB	Output is correct
4	Correct	2 ms	572 KB	Output is correct
5	Correct	2 ms	680 KB	Output is correct

Subtask #2
5.0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	700 KB	Output is correct
2	Correct	2 ms	720 KB	Output is correct
3	Correct	2 ms	728 KB	Output is correct
4	Correct	2 ms	732 KB	Output is correct
5	Correct	2 ms	736 KB	Output is correct
6	Correct	23 ms	3428 KB	Output is correct
7	Correct	13 ms	3428 KB	Output is correct
8	Correct	51 ms	6608 KB	Output is correct
9	Correct	15 ms	6608 KB	Output is correct
10	Correct	56 ms	7936 KB	Output is correct

Subtask #3
10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	7936 KB	Output is correct
2	Correct	2 ms	7936 KB	Output is correct
3	Correct	2 ms	7936 KB	Output is correct
4	Correct	1 ms	7936 KB	Output is correct
5	Correct	2 ms	7936 KB	Output is correct
6	Correct	23 ms	7936 KB	Output is correct
7	Correct	26 ms	7936 KB	Output is correct
8	Correct	50 ms	8372 KB	Output is correct
9	Correct	15 ms	8372 KB	Output is correct
10	Correct	55 ms	9688 KB	Output is correct
11	Correct	2 ms	9688 KB	Output is correct
12	Correct	2 ms	9688 KB	Output is correct
13	Correct	7 ms	9688 KB	Output is correct
14	Correct	2 ms	9688 KB	Output is correct
15	Correct	16 ms	9688 KB	Output is correct

Subtask #4
5.0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	9688 KB	Output is correct
2	Correct	1 ms	9688 KB	Output is correct
3	Correct	2 ms	9688 KB	Output is correct
4	Correct	1 ms	9688 KB	Output is correct
5	Correct	2 ms	9688 KB	Output is correct

Subtask #5
10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	9688 KB	Output is correct
2	Correct	1 ms	9688 KB	Output is correct
3	Correct	1 ms	9688 KB	Output is correct
4	Correct	2 ms	9688 KB	Output is correct
5	Correct	2 ms	9688 KB	Output is correct
6	Correct	1 ms	9688 KB	Output is correct
7	Correct	2 ms	9688 KB	Output is correct
8	Correct	2 ms	9688 KB	Output is correct
9	Correct	2 ms	9688 KB	Output is correct
10	Correct	2 ms	9688 KB	Output is correct

Subtask #6
20.0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	9688 KB	Output is correct
2	Correct	2 ms	9688 KB	Output is correct
3	Correct	1 ms	9688 KB	Output is correct
4	Correct	1 ms	9688 KB	Output is correct
5	Correct	2 ms	9688 KB	Output is correct
6	Correct	2 ms	9688 KB	Output is correct
7	Correct	2 ms	9688 KB	Output is correct
8	Correct	2 ms	9688 KB	Output is correct
9	Correct	2 ms	9688 KB	Output is correct
10	Correct	2 ms	9688 KB	Output is correct
11	Correct	11 ms	9688 KB	Output is correct
12	Correct	14 ms	9688 KB	Output is correct
13	Correct	30 ms	9688 KB	Output is correct
14	Correct	13 ms	9688 KB	Output is correct
15	Correct	27 ms	9688 KB	Output is correct

Subtask #7
5.0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	9688 KB	Output is correct
2	Correct	1 ms	9688 KB	Output is correct
3	Correct	1 ms	9688 KB	Output is correct

Subtask #8
15.0 / 15.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	9688 KB	Output is correct
2	Correct	2 ms	9688 KB	Output is correct
3	Correct	1 ms	9688 KB	Output is correct
4	Correct	1 ms	9688 KB	Output is correct
5	Correct	2 ms	9688 KB	Output is correct
6	Correct	1 ms	9688 KB	Output is correct
7	Correct	2 ms	9688 KB	Output is correct
8	Correct	1 ms	9688 KB	Output is correct

Subtask #9
15.0 / 15.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	9688 KB	Output is correct
2	Correct	1 ms	9688 KB	Output is correct
3	Correct	1 ms	9688 KB	Output is correct
4	Correct	1 ms	9688 KB	Output is correct
5	Correct	1 ms	9688 KB	Output is correct
6	Correct	1 ms	9688 KB	Output is correct
7	Correct	1 ms	9688 KB	Output is correct
8	Correct	1 ms	9688 KB	Output is correct
9	Correct	59 ms	12868 KB	Output is correct
10	Correct	46 ms	12868 KB	Output is correct
11	Correct	17 ms	12868 KB	Output is correct
12	Correct	22 ms	12868 KB	Output is correct
13	Correct	6 ms	12868 KB	Output is correct

Subtask #10
10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	12868 KB	Output is correct
2	Correct	2 ms	12868 KB	Output is correct
3	Correct	2 ms	12868 KB	Output is correct
4	Correct	1 ms	12868 KB	Output is correct
5	Correct	2 ms	12868 KB	Output is correct
6	Correct	2 ms	12868 KB	Output is correct
7	Correct	1 ms	12868 KB	Output is correct
8	Correct	1 ms	12868 KB	Output is correct
9	Correct	60 ms	14276 KB	Output is correct
10	Correct	51 ms	14276 KB	Output is correct
11	Correct	21 ms	14276 KB	Output is correct
12	Correct	21 ms	14276 KB	Output is correct
13	Correct	7 ms	14276 KB	Output is correct
14	Correct	83 ms	16544 KB	Output is correct
15	Correct	104 ms	18176 KB	Output is correct
16	Correct	16 ms	18176 KB	Output is correct
17	Correct	63 ms	18176 KB	Output is correct
18	Correct	31 ms	18176 KB	Output is correct

답안 #43780

Compilation message