답안 #59088 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
59088	2018-07-20T13:36:59 Z	WA_TLE	곤돌라 (IOI14_gondola)	C++14	90 / 100	25 ms	11264 KB

gondola

#include<deque>
#include<queue>
#include<vector>
#include<algorithm>
#include<iostream>
#include<set>
#include<cmath>
#include<tuple>
#include<string>
#include<chrono>
#include<functional>
#include<iterator>
#include<random>
#include<unordered_set>
#include<array>
#include<map>
#include<iomanip>
#include<assert.h>
#include<bitset>
#include<stack>
using namespace std;
typedef long long int llint;
typedef long double lldo;
#define mp make_pair
#define mt make_tuple
#define pub push_back
#define puf push_front
#define pob pop_back
#define pof pop_front
#define fir first
#define sec second
#define res resize
#define ins insert
#define era erase
/*
cout<<setprecision(20)
cin.tie(0);
ios::sync_with_stdio(false);
*/
const llint mod=1000000009;
const llint big=2.19e15+1;
const long double pai=3.141592653589793238462643383279502884197;
const long double eps=1e-15;
template <class T,class U>bool mineq(T& a,U b){if(a>b){a=b;return true;}return false;}
template <class T,class U>bool maxeq(T& a,U b){if(a<b){a=b;return true;}return false;}
llint gcd(llint a,llint b){if(a%b==0){return b;}else return gcd(b,a%b);}
llint lcm(llint a,llint b){if(a==0){return b;}return a/gcd(a,b)*b;}
template<class T> void SO(T& ve){sort(ve.begin(),ve.end());}
template<class T> void REV(T& ve){reverse(ve.begin(),ve.end());}
template<class T>llint LBI(vector<T>&ar,T in){return lower_bound(ar.begin(),ar.end(),in)-ar.begin();}
template<class T>llint UBI(vector<T>&ar,T in){return upper_bound(ar.begin(),ar.end(),in)-ar.begin();}
#include "gondola.h"
int valid(int n, int inputSeq[]){
	static bool use[250001]={0};
	int i,ofset=-1;
	for(i=0;i<n;i++){
		if(use[inputSeq[i]]){return 0;}
		use[inputSeq[i]]=1;
		if(inputSeq[i]>n){continue;}
		int itf=(i+n-inputSeq[i])%n;
		if(ofset==-1||ofset==itf){ofset=itf;}
		else{return 0;}
	}
	return 1;
}

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

int replacement(int n, int gondolaSeq[], int replacementSeq[]){
	int i,dai=0,ofset=0,ziyu=0;
	for(i=0;i<n;i++){
		if(maxeq(dai,gondolaSeq[i])){ziyu=i;}
		if(gondolaSeq[i]>n){continue;}
		int itf=(i+n-gondolaSeq[i])%n;
		ofset=itf;
	}
	//場所-ofset=元のゴンドラ
	for(i=0;i<dai-n;i++){replacementSeq[i]=-1;}
	ziyu=(n+n+ziyu-ofset-1)%n +1;
	for(i=0;i<n;i++){replacementSeq[gondolaSeq[i]-n-1]=(n+n+i-ofset-1)%n +1;}
	for(i=0;i<dai-n;i++){
		if(replacementSeq[i]==-1){
			replacementSeq[i]=ziyu;
			ziyu=i+n+1;
		}
	}
	replacementSeq[dai-n-1]=ziyu;
	return dai-n;
}

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

int countReplacement(int n, int inputSeq[]){
	if(!valid(n,inputSeq)){return 0;}
	llint dai=0,ans=n,zi=0,i;
	static bool ara[250001]={0};
	for(i=0;i<n;i++){
		maxeq(dai,inputSeq[i]);
		ara[inputSeq[i]]=1;
		if(inputSeq[i]<=n){ans=1;}
	}
	for(i=dai;i>n;i--){
		if(ara[i]){zi++;}
		else{ans*=zi;ans%=mod;}
	}
	return ans;
}

Subtask #1
5.0 / 5.0

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

Subtask #2
5.0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	652 KB	Output is correct
2	Correct	4 ms	652 KB	Output is correct
3	Correct	2 ms	652 KB	Output is correct
4	Correct	3 ms	652 KB	Output is correct
5	Correct	4 ms	656 KB	Output is correct
6	Correct	9 ms	1044 KB	Output is correct
7	Correct	18 ms	1632 KB	Output is correct
8	Correct	16 ms	2000 KB	Output is correct
9	Correct	8 ms	2000 KB	Output is correct
10	Correct	22 ms	2660 KB	Output is correct

Subtask #3
10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	3 ms	2660 KB	Output is correct
2	Correct	2 ms	2660 KB	Output is correct
3	Correct	3 ms	2660 KB	Output is correct
4	Correct	3 ms	2660 KB	Output is correct
5	Correct	3 ms	2660 KB	Output is correct
6	Correct	9 ms	2768 KB	Output is correct
7	Correct	17 ms	3376 KB	Output is correct
8	Correct	15 ms	3724 KB	Output is correct
9	Correct	7 ms	3724 KB	Output is correct
10	Correct	16 ms	4384 KB	Output is correct
11	Correct	3 ms	4384 KB	Output is correct
12	Correct	2 ms	4384 KB	Output is correct
13	Correct	10 ms	4488 KB	Output is correct
14	Correct	2 ms	4488 KB	Output is correct
15	Correct	17 ms	5116 KB	Output is correct

Subtask #4
5.0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Correct	3 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	3 ms	5116 KB	Output is correct

Subtask #5
10.0 / 10.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	4 ms	5116 KB	Output is correct
6	Correct	4 ms	5116 KB	Output is correct
7	Correct	2 ms	5116 KB	Output is correct
8	Correct	3 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	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	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	3 ms	5116 KB	Output is correct
8	Correct	3 ms	5116 KB	Output is correct
9	Correct	4 ms	5116 KB	Output is correct
10	Correct	2 ms	5116 KB	Output is correct
11	Correct	14 ms	6008 KB	Output is correct
12	Correct	18 ms	6588 KB	Output is correct
13	Correct	15 ms	7096 KB	Output is correct
14	Correct	13 ms	7176 KB	Output is correct
15	Correct	25 ms	8384 KB	Output is correct

Subtask #7
5.0 / 5.0

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

Subtask #8
15.0 / 15.0

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

Subtask #9
15.0 / 15.0

#	결과	실행 시간	메모리	Grader output
1	Correct	3 ms	8384 KB	Output is correct
2	Correct	2 ms	8384 KB	Output is correct
3	Correct	2 ms	8384 KB	Output is correct
4	Correct	2 ms	8384 KB	Output is correct
5	Correct	2 ms	8384 KB	Output is correct
6	Correct	3 ms	8384 KB	Output is correct
7	Correct	2 ms	8384 KB	Output is correct
8	Correct	3 ms	8384 KB	Output is correct
9	Correct	19 ms	8384 KB	Output is correct
10	Correct	15 ms	8384 KB	Output is correct
11	Correct	9 ms	8480 KB	Output is correct
12	Correct	9 ms	8636 KB	Output is correct
13	Correct	5 ms	8636 KB	Output is correct

Subtask #10
0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	8636 KB	Output is correct
2	Correct	3 ms	8636 KB	Output is correct
3	Correct	2 ms	8636 KB	Output is correct
4	Correct	3 ms	8636 KB	Output is correct
5	Correct	2 ms	8636 KB	Output is correct
6	Correct	2 ms	8636 KB	Output is correct
7	Correct	2 ms	8636 KB	Output is correct
8	Correct	2 ms	8636 KB	Output is correct
9	Correct	16 ms	9508 KB	Output is correct
10	Correct	14 ms	9732 KB	Output is correct
11	Correct	8 ms	9860 KB	Output is correct
12	Correct	12 ms	10016 KB	Output is correct
13	Correct	5 ms	10016 KB	Output is correct
14	Runtime error	18 ms	11264 KB	Execution killed with signal 11 (could be triggered by violating memory limits)
15	Halted	0 ms	0 KB	-

답안 #59088

Compilation message