oj.uz

Submission #55642

# Submission time Handle Problem Language Result Execution time Memory
55642 2018-07-08T10:23:46 Z leejseo Gondola (IOI14_gondola) C++
90 / 100
 1000 ms 5144 KB 
#include "gondola.h"
#include <vector>
#include <algorithm>
#include <utility>
using namespace std;

#define UNDEF -1

typedef pair<int, int> pii;
long long mod = 1000000009;

int valid(int n, int inputSeq[])
{
	vector<int> L;
	L.resize(n);
	int temp;
	int shift = -1;
	for (int i=0; i<n; i++){
		L[i] = inputSeq[i];
		if (L[i] <= n){
			temp = (i-L[i]+n+1)%n;
			if (shift == UNDEF) shift = temp;
			else if (shift != temp) return 0;
		}
	}
	sort(L.begin(), L.end());
	for (int i=1; i<n; i++) if (L[i-1] == L[i]) return 0;
	L.clear();
	return 1;
}

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

int replacement(int n, int gondolaSeq[], int replacementSeq[])
{
  int min_val = 1000000, min_index = -1;
	vector<pii> L;
	for (int i=0; i<n; i++){
		if (min_val > gondolaSeq[i]){
			min_index = i;
			min_val = gondolaSeq[i];
		} 
	}	
	bool b = (min_val > n);	
	for (int j=0; j<n; j++){
			int i = min_index + j;
			int c;
			if (b) c = j;
			else{
				c = (j + min_val)%n;
			}	
			L.push_back(pii(gondolaSeq[i%n], (c == 0 ? n : c)));
	}	
	sort(L.begin(), L.end());	
	int l = 0;
	for (int i=0; i<n; i++){		
		while (L[i].first != L[i].second){
			replacementSeq[l] = L[i].second;
			l++;
			L[i].second = n+l;
		}
	}	
	return l;
}

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

long long llpow(long long a, int b){
	long long ans = 1;
	while(b){
		if (b & 1) ans = (ans * a) % mod;
		a = (a*a)%mod;
		b >>=1;
	}	
	return ans;
}


int countReplacement(int n, int inputSeq[])
{
  if (!valid(n, inputSeq)) return 0;
	int min_val = 1000000, min_index = -1;
	vector<int> L;
	for (int i=0; i<n; i++){
		if (min_val > inputSeq[i]){
			min_index = i;
			min_val = inputSeq[i];
		} 
	}	
	bool b = (min_val > n);	
	for (int j=0; j<n; j++){
			int i = min_index + j;
			int c;
			if (b) c = j;
			else{
				c = (j + min_val)%n;
			}	
			if (inputSeq[i%n] != (c == 0? n : c)) L.push_back(inputSeq[i%n]);
	}	
	sort(L.begin(), L.end());	
	long long ans = 1;
	int m = L.size();
	int k = n - m;
	for (int i=0; i<m; i++){
		if (i == 0) {
			ans = (ans * llpow((long long) m, L[i]-n-1))%mod;			
			continue;
		}
		ans = (ans * llpow((long long) m-i, L[i]-1-L[i-1]))%mod;
	}	
	if (m == n) ans = (ans * n) % mod;
	return (int) ans;
}

Compilation message

gondola.cpp: In function 'int countReplacement(int, int*)':
gondola.cpp:103:6: warning: unused variable 'k' [-Wunused-variable]
  int k = n - m;
      ^

Subtask #1
5.0 / 5.0

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

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 568 KB Output is correct
2 Correct 2 ms 568 KB Output is correct
3 Correct 2 ms 568 KB Output is correct
4 Correct 3 ms 568 KB Output is correct
5 Correct 2 ms 600 KB Output is correct
6 Correct 11 ms 856 KB Output is correct
7 Correct 14 ms 1252 KB Output is correct
8 Correct 15 ms 1252 KB Output is correct
9 Correct 8 ms 1252 KB Output is correct
10 Correct 27 ms 1260 KB Output is correct

Subtask #3
10.0 / 10.0

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

Subtask #4
5.0 / 5.0

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

Subtask #5
10.0 / 10.0

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

Subtask #6
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1276 KB Output is correct
2 Correct 2 ms 1276 KB Output is correct
3 Correct 2 ms 1276 KB Output is correct
4 Correct 2 ms 1276 KB Output is correct
5 Correct 3 ms 1276 KB Output is correct
6 Correct 3 ms 1276 KB Output is correct
7 Correct 3 ms 1276 KB Output is correct
8 Correct 3 ms 1276 KB Output is correct
9 Correct 3 ms 1276 KB Output is correct
10 Correct 3 ms 1276 KB Output is correct
11 Correct 17 ms 2084 KB Output is correct
12 Correct 16 ms 2084 KB Output is correct
13 Correct 23 ms 2084 KB Output is correct
14 Correct 17 ms 2228 KB Output is correct
15 Correct 27 ms 2584 KB Output is correct

Subtask #7
5.0 / 5.0

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

Subtask #8
15.0 / 15.0

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

Subtask #9
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2584 KB Output is correct
2 Correct 3 ms 2584 KB Output is correct
3 Correct 2 ms 2584 KB Output is correct
4 Correct 2 ms 2584 KB Output is correct
5 Correct 2 ms 2584 KB Output is correct
6 Correct 2 ms 2584 KB Output is correct
7 Correct 2 ms 2584 KB Output is correct
8 Correct 2 ms 2584 KB Output is correct
9 Correct 32 ms 2584 KB Output is correct
10 Correct 31 ms 2584 KB Output is correct
11 Correct 13 ms 2584 KB Output is correct
12 Correct 13 ms 2584 KB Output is correct
13 Correct 7 ms 2584 KB Output is correct

Subtask #10
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2584 KB Output is correct
2 Correct 2 ms 2584 KB Output is correct
3 Correct 2 ms 2584 KB Output is correct
4 Correct 2 ms 2584 KB Output is correct
5 Correct 2 ms 2584 KB Output is correct
6 Correct 3 ms 2584 KB Output is correct
7 Correct 3 ms 2584 KB Output is correct
8 Correct 2 ms 2584 KB Output is correct
9 Correct 43 ms 3052 KB Output is correct
10 Correct 23 ms 3448 KB Output is correct
11 Correct 11 ms 3448 KB Output is correct
12 Correct 14 ms 3524 KB Output is correct
13 Correct 6 ms 3524 KB Output is correct
14 Execution timed out 1085 ms 5144 KB Time limit exceeded
15 Halted 0 ms 0 KB -