oj.uz

Submission #59088

# Submission time Handle Problem Language Result Execution time Memory
59088 2018-07-20T13:36:59 Z WA_TLE Gondola (IOI14_gondola) C++14
90 / 100
 25 ms 11264 KB 
#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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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 -