oj.uz

Submission #43780

# Submission time Handle Problem Language Result Execution time Memory
43780 2018-03-23T15:56:07 Z faustaadp Gondola (IOI14_gondola) C++14
100 / 100
 104 ms 18176 KB 
#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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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