oj.uz

Submission #91192

# Submission time Handle Problem Language Result Execution time Memory
91192 2018-12-26T13:43:28 Z arman_ferdous Gondola (IOI14_gondola) C++17
100 / 100
 59 ms 16572 KB 
#include "gondola.h"
#include <bits/stdc++.h>
using namespace std;

set<int> st;
int valid(int n, int inputSeq[]) {
	int last = -1, start = -1, num = 1000000;
	for(int i = 0; i < n; i++) {
		st.insert(inputSeq[i]);
		if(inputSeq[i] > n) inputSeq[i] = -1;
		else {
			last = i;
			if(inputSeq[i] < num) 
				start = i, num = inputSeq[i];
		}
	}
	if(st.size() != n) return 0;
	if(last == -1) return 1;
	for(int i = start; i < n; i++)
		if(inputSeq[i] + 1 && inputSeq[i] != num + i - start)
			return 0;
	int at0 = inputSeq[last] + n - last;
	for(int i = 0; i < start; i++)
		if(inputSeq[i] + 1 && inputSeq[i] != at0 + i)
			return 0;

  	return 1;
}

int init[100001];
vector< pair<int,int> > v;
int replacement(int n, int gondolaSeq[], int replacementSeq[]) {
	int start = -1;
 	for(int i = 0; i < n; i++) if(gondolaSeq[i] <= n) {
		start = i - gondolaSeq[i] + 1;
		if(start < 0) start += n;
		break;
	} if(start == -1) start = 0;
	int cur = 1;
 	for(int i = start; i < n; i++) init[i] = cur++;
 	for(int i = 0; i < start; i++) init[i] = cur++;

 	for(int i = 0; i < n; i++) if(gondolaSeq[i] > n)
 		v.push_back({gondolaSeq[i], i});
 	sort(v.begin(), v.end());

 	int ptr = 0;
 	for(auto it : v) {
 		while(cur <= it.first) {
 			replacementSeq[ptr++] = init[it.second];
 			init[it.second] = cur;
 			cur++;
 		}
 	} return ptr;
}

typedef long long ll;
const int MOD = 1e9+9;

ll powmod(ll a, ll b) {
	ll ret = 1;
	while(b > 0) {
		if(b & 1) ret = (ret * a) % MOD;
		a = (a * a) % MOD;
		b >>= 1;
	} return ret;
}

int tmp[100001];
vector<int> vals;
int countReplacement(int n, int inputSeq[]) {
	for(int i = 0; i < n; i++) 
		tmp[i] = inputSeq[i];
	if(!valid(n,tmp)) return 0;
	
	int start = -1, last = n;
	ll slot = 0;
	for(int i = 0; i < n; i++) {
		if(inputSeq[i] > n) {
			slot++;
			vals.push_back(inputSeq[i]);
		}
		else start = 1;
	} sort(vals.begin(), vals.end());

	ll ret = (start == -1 ? n : 1);
	for(int x : vals) {
		ll choices = x - last - 1;
		ret = ret * powmod(slot, choices) % MOD;
		last = x;
		slot--;
	} return ret;
}

Compilation message

gondola.cpp: In function 'int valid(int, int*)':
gondola.cpp:17:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  if(st.size() != n) return 0;
     ~~~~~~~~~~^~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 456 KB Output is correct
3 Correct 2 ms 468 KB Output is correct
4 Correct 2 ms 476 KB Output is correct
5 Correct 2 ms 520 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 524 KB Output is correct
2 Correct 2 ms 528 KB Output is correct
3 Correct 2 ms 532 KB Output is correct
4 Correct 2 ms 532 KB Output is correct
5 Correct 2 ms 540 KB Output is correct
6 Correct 13 ms 2592 KB Output is correct
7 Correct 33 ms 4576 KB Output is correct
8 Correct 24 ms 5172 KB Output is correct
9 Correct 8 ms 5172 KB Output is correct
10 Correct 29 ms 6380 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 6380 KB Output is correct
2 Correct 2 ms 6380 KB Output is correct
3 Correct 2 ms 6380 KB Output is correct
4 Correct 2 ms 6380 KB Output is correct
5 Correct 2 ms 6380 KB Output is correct
6 Correct 12 ms 6380 KB Output is correct
7 Correct 35 ms 6400 KB Output is correct
8 Correct 24 ms 7032 KB Output is correct
9 Correct 8 ms 7032 KB Output is correct
10 Correct 30 ms 7820 KB Output is correct
11 Correct 2 ms 7820 KB Output is correct
12 Correct 2 ms 7820 KB Output is correct
13 Correct 17 ms 7820 KB Output is correct
14 Correct 2 ms 7820 KB Output is correct
15 Correct 45 ms 8820 KB Output is correct

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 8820 KB Output is correct
2 Correct 2 ms 8820 KB Output is correct
3 Correct 2 ms 8820 KB Output is correct
4 Correct 2 ms 8820 KB Output is correct
5 Correct 2 ms 8820 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 8820 KB Output is correct
2 Correct 2 ms 8820 KB Output is correct
3 Correct 2 ms 8820 KB Output is correct
4 Correct 2 ms 8820 KB Output is correct
5 Correct 2 ms 8820 KB Output is correct
6 Correct 2 ms 8820 KB Output is correct
7 Correct 2 ms 8820 KB Output is correct
8 Correct 2 ms 8820 KB Output is correct
9 Correct 2 ms 8820 KB Output is correct
10 Correct 2 ms 8820 KB Output is correct

Subtask #6
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 8820 KB Output is correct
2 Correct 2 ms 8820 KB Output is correct
3 Correct 2 ms 8820 KB Output is correct
4 Correct 2 ms 8820 KB Output is correct
5 Correct 2 ms 8820 KB Output is correct
6 Correct 2 ms 8820 KB Output is correct
7 Correct 2 ms 8820 KB Output is correct
8 Correct 2 ms 8820 KB Output is correct
9 Correct 2 ms 8820 KB Output is correct
10 Correct 2 ms 8820 KB Output is correct
11 Correct 10 ms 8820 KB Output is correct
12 Correct 11 ms 8820 KB Output is correct
13 Correct 15 ms 8820 KB Output is correct
14 Correct 10 ms 8820 KB Output is correct
15 Correct 20 ms 8820 KB Output is correct

Subtask #7
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 8820 KB Output is correct
2 Correct 2 ms 8820 KB Output is correct
3 Correct 2 ms 8820 KB Output is correct

Subtask #8
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 8820 KB Output is correct
2 Correct 2 ms 8820 KB Output is correct
3 Correct 2 ms 8820 KB Output is correct
4 Correct 2 ms 8820 KB Output is correct
5 Correct 2 ms 8820 KB Output is correct
6 Correct 2 ms 8820 KB Output is correct
7 Correct 2 ms 8820 KB Output is correct
8 Correct 2 ms 8820 KB Output is correct

Subtask #9
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 8820 KB Output is correct
2 Correct 2 ms 8820 KB Output is correct
3 Correct 2 ms 8820 KB Output is correct
4 Correct 2 ms 8820 KB Output is correct
5 Correct 2 ms 8820 KB Output is correct
6 Correct 2 ms 8820 KB Output is correct
7 Correct 2 ms 8820 KB Output is correct
8 Correct 2 ms 8820 KB Output is correct
9 Correct 42 ms 11392 KB Output is correct
10 Correct 36 ms 11392 KB Output is correct
11 Correct 12 ms 11392 KB Output is correct
12 Correct 15 ms 11392 KB Output is correct
13 Correct 5 ms 11392 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 11392 KB Output is correct
2 Correct 2 ms 11392 KB Output is correct
3 Correct 2 ms 11392 KB Output is correct
4 Correct 2 ms 11392 KB Output is correct
5 Correct 2 ms 11392 KB Output is correct
6 Correct 2 ms 11392 KB Output is correct
7 Correct 2 ms 11392 KB Output is correct
8 Correct 2 ms 11392 KB Output is correct
9 Correct 43 ms 12684 KB Output is correct
10 Correct 32 ms 12684 KB Output is correct
11 Correct 13 ms 12684 KB Output is correct
12 Correct 16 ms 12684 KB Output is correct
13 Correct 4 ms 12684 KB Output is correct
14 Correct 57 ms 15112 KB Output is correct
15 Correct 59 ms 16572 KB Output is correct
16 Correct 11 ms 16572 KB Output is correct
17 Correct 39 ms 16572 KB Output is correct
18 Correct 21 ms 16572 KB Output is correct