oj.uz

Submission #59094

# Submission time Handle Problem Language Result Execution time Memory
59094 2018-07-20T13:56:54 Z WA_TLE Gondola (IOI14_gondola) C++14
70 / 100
 137 ms 6756 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[]){
	map<int,bool>use;
	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;
		}
	}
	if(dai>n){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;
	for(i=0;i<n;i++){
		maxeq(dai,inputSeq[i]);
		if(inputSeq[i]<=n){ans=1;}
	}
	sort(inputSeq,inputSeq+n);
	int mae=dai+1;
	for(i=n-1;i>=0&&inputSeq[i]>n;i--){
		int dis=mae-inputSeq[i]-1;
		mae=inputSeq[i];
		llint bg=zi;
		for(int h=0;h<=30;h++){
			if(dis&(1<<h)){ans*=bg;ans%=mod;}
			bg*=bg;bg%=mod;
		}
		zi++;
	}
	int dis=mae-n-1;
	llint bg=zi;
		for(int h=0;h<=30;h++){
			if(dis&(1<<h)){ans*=bg;ans%=mod;}
			bg*=bg;bg%=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 3 ms 376 KB Output is correct
3 Correct 4 ms 564 KB Output is correct
4 Correct 2 ms 564 KB Output is correct
5 Correct 2 ms 564 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 564 KB Output is correct
2 Correct 3 ms 596 KB Output is correct
3 Correct 2 ms 596 KB Output is correct
4 Correct 4 ms 596 KB Output is correct
5 Correct 2 ms 620 KB Output is correct
6 Correct 28 ms 2412 KB Output is correct
7 Correct 15 ms 2412 KB Output is correct
8 Correct 34 ms 4204 KB Output is correct
9 Correct 12 ms 4204 KB Output is correct
10 Correct 49 ms 4832 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4832 KB Output is correct
2 Correct 2 ms 4832 KB Output is correct
3 Correct 2 ms 4832 KB Output is correct
4 Correct 2 ms 4832 KB Output is correct
5 Correct 2 ms 4832 KB Output is correct
6 Correct 24 ms 4832 KB Output is correct
7 Correct 16 ms 4832 KB Output is correct
8 Correct 40 ms 4832 KB Output is correct
9 Correct 13 ms 4832 KB Output is correct
10 Correct 53 ms 4860 KB Output is correct
11 Correct 2 ms 4860 KB Output is correct
12 Correct 2 ms 4860 KB Output is correct
13 Correct 8 ms 4860 KB Output is correct
14 Correct 2 ms 4860 KB Output is correct
15 Correct 14 ms 4860 KB Output is correct

Subtask #4
5.0 / 5.0

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

Subtask #5
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4860 KB Output is correct
2 Correct 2 ms 4860 KB Output is correct
3 Correct 2 ms 4860 KB Output is correct
4 Correct 2 ms 4860 KB Output is correct
5 Correct 2 ms 4860 KB Output is correct
6 Correct 3 ms 4860 KB Output is correct
7 Runtime error 5 ms 4860 KB Execution killed with signal 11 (could be triggered by violating memory limits)
8 Halted 0 ms 0 KB -

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4860 KB Output is correct
2 Correct 3 ms 4860 KB Output is correct
3 Correct 3 ms 4860 KB Output is correct
4 Correct 2 ms 4860 KB Output is correct
5 Correct 2 ms 4860 KB Output is correct
6 Correct 2 ms 4860 KB Output is correct
7 Runtime error 3 ms 4860 KB Execution killed with signal 11 (could be triggered by violating memory limits)
8 Halted 0 ms 0 KB -

Subtask #7
5.0 / 5.0

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

Subtask #8
15.0 / 15.0

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

Subtask #9
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4860 KB Output is correct
2 Correct 2 ms 4860 KB Output is correct
3 Correct 2 ms 4860 KB Output is correct
4 Correct 2 ms 4860 KB Output is correct
5 Correct 2 ms 4860 KB Output is correct
6 Correct 2 ms 4860 KB Output is correct
7 Correct 2 ms 4860 KB Output is correct
8 Correct 2 ms 4860 KB Output is correct
9 Correct 81 ms 4860 KB Output is correct
10 Correct 75 ms 4860 KB Output is correct
11 Correct 25 ms 4860 KB Output is correct
12 Correct 34 ms 4860 KB Output is correct
13 Correct 9 ms 4860 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4860 KB Output is correct
2 Correct 2 ms 4860 KB Output is correct
3 Correct 3 ms 4860 KB Output is correct
4 Correct 3 ms 4860 KB Output is correct
5 Correct 2 ms 4860 KB Output is correct
6 Correct 3 ms 4860 KB Output is correct
7 Correct 3 ms 4860 KB Output is correct
8 Correct 3 ms 4860 KB Output is correct
9 Correct 97 ms 4860 KB Output is correct
10 Correct 60 ms 4860 KB Output is correct
11 Correct 28 ms 4860 KB Output is correct
12 Correct 34 ms 4860 KB Output is correct
13 Correct 9 ms 4860 KB Output is correct
14 Correct 96 ms 5108 KB Output is correct
15 Correct 137 ms 6756 KB Output is correct
16 Correct 20 ms 6756 KB Output is correct
17 Correct 90 ms 6756 KB Output is correct
18 Correct 46 ms 6756 KB Output is correct