답안 #72919 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
72919	2018-08-27T08:38:07 Z	nvmdava	곤돌라 (IOI14_gondola)	C++17	100 / 100	93 ms	5116 KB

gondola

#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);
			ans %= MOD;
		}
		mx = x.val + 1;
	}
	if(in){
		ans = ans * n % MOD;
		return ans;
	}
	return (int) ans;
}

Subtask #1
5.0 / 5.0

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

Subtask #2
5.0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Correct	3 ms	620 KB	Output is correct
2	Correct	2 ms	620 KB	Output is correct
3	Correct	3 ms	620 KB	Output is correct
4	Correct	3 ms	748 KB	Output is correct
5	Correct	2 ms	748 KB	Output is correct
6	Correct	23 ms	2684 KB	Output is correct
7	Correct	17 ms	2684 KB	Output is correct
8	Correct	36 ms	4476 KB	Output is correct
9	Correct	12 ms	4476 KB	Output is correct
10	Correct	52 ms	5116 KB	Output is correct

Subtask #3
10.0 / 10.0

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

Subtask #4
5.0 / 5.0

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

Subtask #5
10.0 / 10.0

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

Subtask #6
20.0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	3 ms	5116 KB	Output is correct
2	Correct	2 ms	5116 KB	Output is correct
3	Correct	2 ms	5116 KB	Output is correct
4	Correct	2 ms	5116 KB	Output is correct
5	Correct	2 ms	5116 KB	Output is correct
6	Correct	2 ms	5116 KB	Output is correct
7	Correct	2 ms	5116 KB	Output is correct
8	Correct	2 ms	5116 KB	Output is correct
9	Correct	3 ms	5116 KB	Output is correct
10	Correct	3 ms	5116 KB	Output is correct
11	Correct	19 ms	5116 KB	Output is correct
12	Correct	21 ms	5116 KB	Output is correct
13	Correct	34 ms	5116 KB	Output is correct
14	Correct	24 ms	5116 KB	Output is correct
15	Correct	36 ms	5116 KB	Output is correct

Subtask #7
5.0 / 5.0

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

Subtask #8
15.0 / 15.0

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

Subtask #9
15.0 / 15.0

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

Subtask #10
10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	5116 KB	Output is correct
2	Correct	3 ms	5116 KB	Output is correct
3	Correct	2 ms	5116 KB	Output is correct
4	Correct	2 ms	5116 KB	Output is correct
5	Correct	3 ms	5116 KB	Output is correct
6	Correct	3 ms	5116 KB	Output is correct
7	Correct	3 ms	5116 KB	Output is correct
8	Correct	3 ms	5116 KB	Output is correct
9	Correct	23 ms	5116 KB	Output is correct
10	Correct	19 ms	5116 KB	Output is correct
11	Correct	9 ms	5116 KB	Output is correct
12	Correct	10 ms	5116 KB	Output is correct
13	Correct	5 ms	5116 KB	Output is correct
14	Correct	45 ms	5116 KB	Output is correct
15	Correct	34 ms	5116 KB	Output is correct
16	Correct	10 ms	5116 KB	Output is correct
17	Correct	25 ms	5116 KB	Output is correct
18	Correct	21 ms	5116 KB	Output is correct

답안 #72919

Compilation message