답안 #72918 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
72918	2018-08-27T08:37:20 Z	nvmdava	곤돌라 (IOI14_gondola)	C++17	60 / 100	66 ms	5204 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);
		}
		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	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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	-

답안 #72918

Compilation message