oj.uz

Submission #72918

# Submission time Handle Problem Language Result Execution time Memory
72918 2018-08-27T08:37:20 Z nvmdava Gondola (IOI14_gondola) C++17
60 / 100
 66 ms 5204 KB 
#include "gondola.h"
#include <bits/stdc++.h>
#define MOD 1000000009
using namespace std;
 
struct Gondola{
	int id, val;
	Gondola(int _id, int _val){
		id = _id;
		val = _val;
	}
	bool operator<(const Gondola& rhs) const{
		return val < rhs.val;
	}
};
 
int ord[100001];
map<int, int> in;
vector<Gondola> v;
 
 
int valid(int n, int inputSeq[]){
	int i;
	for(i = 0; i < n; i++){
		if(in[inputSeq[i]]) return 0;
		in[inputSeq[i]] = 1;
	}
	for(i = 0; i < n; i++){
		if(inputSeq[i] <= n) break;
	}
	if(i == n) return 1;
	int k = inputSeq[i] - 1;
	for(int j = 0; j < n; j++){
		ord[(k + j) % n] = inputSeq[(i + j) % n];
		if((ord[(k + j) % n] != (k + j) % n + 1 && ord[(k + j) % n] <= n) || ord[(k + j) % n] < 1) return 0;
	}
	for(i = 0; i < n; i++){
		if((ord[i] != i + 1 && ord[i] <= n) || ord[i] < 1) return 0;
	}
	return 1;
}
 
//----------------------
 
int replacement(int n, int gondolaSeq[], int replacementSeq[]){
	int i;
	for(i = 0; i < n; i++){
		if(gondolaSeq[i] <= n) break;
	}
	int k;
	if(i == n){
		i = 0;
		k = 0;
	} else {
		k = gondolaSeq[i] - 1;	
	}
	for(int j = 0; j < n; j++){
		v.push_back(Gondola((k + j) % n + 1, gondolaSeq[(i + j) % n]));
	}
	sort(v.begin(), v.end());
	i = 0;
	int s = n + 1;
	for(auto x : v){
		if(x.val <= n) continue;
		replacementSeq[i] = x.id;
		i++;
		for(; s < x.val; s++){
			replacementSeq[i] = s;
			i++;
		}
		s = x.val + 1;
	}
	return i;
}
 
//----------------------
long long pow(long long x, int p){
	long long s = 1;
	while(p > 0){
		if(p % 2 == 1){
			s *= x;
			s %= MOD;
		}
		x *= x;
		x %= MOD;
		p /= 2;
	}
	return s;
}

int countReplacement(int n, int gondolaSeq[]){
	int i;
	for(i = 0; i < n; i++){
		if(gondolaSeq[i] <= n) break;
	}
	bool in = 0;
	int k;
	if(i == n){
		i = 0;
		k = 0;
		in = 1;
	} else {
		k = gondolaSeq[i] - 1;	
	}
	for(int j = 0; j < n; j++){
		v.push_back(Gondola((k + j) % n + 1, gondolaSeq[(i + j) % n]));
	}
	sort(v.begin(), v.end());
	i = 0;
	long long ans = 1;
	int mx = n + 1;
	long long mlt = n + 1;
	for(auto x : v){
		mlt--;
		if(x.val < mx) continue;
		if(mx < x.val){
			ans = ans * pow(mlt, x.val - mx);
		}
		mx = x.val + 1;
	}
	if(in){
		ans = ans * n % MOD;
		return ans;
	}
	return (int) ans;
}

Subtask #1
5.0 / 5.0

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

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 484 KB Output is correct
2 Correct 3 ms 520 KB Output is correct
3 Correct 4 ms 520 KB Output is correct
4 Correct 3 ms 568 KB Output is correct
5 Correct 3 ms 568 KB Output is correct
6 Correct 22 ms 2560 KB Output is correct
7 Correct 22 ms 2560 KB Output is correct
8 Correct 35 ms 4408 KB Output is correct
9 Correct 13 ms 4408 KB Output is correct
10 Correct 55 ms 5076 KB Output is correct

Subtask #3
10.0 / 10.0

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

Subtask #4
5.0 / 5.0

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

Subtask #5
10.0 / 10.0

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

Subtask #6
20.0 / 20.0

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

Subtask #7
5.0 / 5.0

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

Subtask #8
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 5204 KB Output is correct
2 Correct 3 ms 5204 KB Output is correct
3 Correct 4 ms 5204 KB Output is correct
4 Correct 2 ms 5204 KB Output is correct
5 Correct 2 ms 5204 KB Output is correct
6 Correct 2 ms 5204 KB Output is correct
7 Incorrect 2 ms 5204 KB Integer 1676884508 violates the range [0, 1000000008]
8 Halted 0 ms 0 KB -

Subtask #9
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5204 KB Output is correct
2 Correct 2 ms 5204 KB Output is correct
3 Correct 2 ms 5204 KB Output is correct
4 Correct 2 ms 5204 KB Output is correct
5 Correct 2 ms 5204 KB Output is correct
6 Correct 2 ms 5204 KB Output is correct
7 Incorrect 3 ms 5204 KB Integer 1676884508 violates the range [0, 1000000008]
8 Halted 0 ms 0 KB -

Subtask #10
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5204 KB Output is correct
2 Correct 2 ms 5204 KB Output is correct
3 Correct 4 ms 5204 KB Output is correct
4 Correct 3 ms 5204 KB Output is correct
5 Correct 2 ms 5204 KB Output is correct
6 Correct 2 ms 5204 KB Output is correct
7 Incorrect 3 ms 5204 KB Integer 1676884508 violates the range [0, 1000000008]
8 Halted 0 ms 0 KB -