oj.uz

답안 #200787

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
200787 2020-02-08T07:11:09 Z mohammad 곤돌라 (IOI14_gondola) C++14
20 / 100
 44 ms 5744 KB 
/*
░░░░██████████████████
░░▄███████▀▀▀▀▀▀███████▄
░▐████▀▒mohammad▒▀██████▄
░███▀▒▒▒▒alaa▒▒▒▒▒▒▀█████
░▐██▒▒▒alwrawrah▒▒▒▒▒████▌
░▐█▌▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒▒████▌
░░█▒▄▀▀▀▀▀▄▒▒▄▀▀▀▀▀▄▒▐███▌
░░░▐░░░▄▄░░▌▐░░░▄▄░░▌▐███▌
░▄▀▌░░░▀▀░░▌▐░░░▀▀░░▌▒▀▒█▌
░▌▒▀▄░░░░▄▀▒▒▀▄░░░▄▀▒▒▄▀▒▌
░▀▄▐▒▀▀▀▀▒▒▒▒▒▒▀▀▀▒▒▒▒▒▒█
░░░▀▌▒▄██▄▄▄▄████▄▒▒▒▒█▀
░░░░▄██████████████▒▒▐▌
░░░▀███▀▀████▀█████▀▒▌
░░░░░▌▒▒▒▄▒▒▒▄▒▒▒▒▒▒▐
░░░░░▌▒▒▒▒▀▀▀▒▒▒▒▒▒▒▐
*/
 
#include<bits/stdc++.h>
#include "gondola.h"
using namespace std;
 
typedef long long ll ;
const ll oo = 4294967296 ;
const double PI = acos(-1) ;
const ll M = 1e9 + 9   ;

map<int,int> mp;
vector<pair<int,int>> v;
pair<int, int> p[1000010] , rp[1000010] ;

int valid(int n, int inputSeq[]){
	return -1 ;
}

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

int replacement(int n, int gondolaSeq[], int replacementSeq[]){
	return -2;
}

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

ll fastpower( ll x , ll n ){
	ll res = 1 ;
	while(n > 0){
		if(n % 2 == 1)
			res = (res * x) % M;
		x = ( x * x ) % M;
		n = n / 2 ;
	}
	return res;
}

int countReplacement(int n, int inputSeq[]){
	bool b = false ;
	for(int i = 0 ; i < n ; ++i){
		p[i] = {inputSeq[i] , i + 1};
		rp[i] = {inputSeq[i] , n - i};
		mp[inputSeq[i]]++;
		if(mp[inputSeq[i]] > 1)return 0;
		if(inputSeq[i] <= n){
			b = 1;
			int x = inputSeq[i];
			int f = i - 1;
			while(f > -1 && inputSeq[f] > n){
				x--;
				if(x == 0) x = n;
				v.push_back({inputSeq[f] , x});
				inputSeq[f] = x;
				mp[x]++;	
				if(mp[x] > 1) return 0 ;
				f--;
			}
			f = i + 1 ;
			x = inputSeq[i];
			while(f < n && inputSeq[f] > n){
				x++;
				if(x == n + 1) x = 1;
				v.push_back({inputSeq[f] , x});
				inputSeq[f] = x;
				mp[x]++;
				if(mp[x] > 1)return 0;
				f++;
			}
			i = f - 1;
		}
	}
	ll ans = 1 , ls = n + 1 , ans1 = 1;
	if(b){
		for(int i = 1 ; i < n ; ++i)
			if((inputSeq[i] == 1 && inputSeq[i - 1] != n) || (inputSeq[i] != 1 && inputSeq[i - 1] + 1 != inputSeq[i])) return 0;
		sort(v.begin(), v.end());
		int idx = 0 ;
		for(auto x : v){
			if(x.first == v.back().first) continue ;
			ans = (ans * fastpower(v.size() - idx , x.first - ls)) % M;
			ls = x.first + 1 ;
			idx++;
		}
	}else{
		int idx = 0 ;
		sort(p , p + n);
		sort(rp , rp + n);
		for(int i = 0 ; i < n - 1 ; ++i){
			ans = (ans * fastpower(v.size() - idx , p[i].first - ls)) % M;
			ls = p[i].first + 1;
			idx++;
		}
		idx = 0;
		ls = n + 1;
		for(int i = 0 ; i < n - 1 ; ++i){
			ans1 = (ans1 * fastpower(v.size() - idx , p[i].first - ls)) % M;
			idx++;
			ls = p[i].first + 1;
		}
		ans = (ans + ans1) % M;
	}
	return ans ;
}

Subtask #1
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 5 ms 376 KB Integer -1 violates the range [0, 1]
2 Halted 0 ms 0 KB -

Subtask #2
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 5 ms 376 KB Integer -1 violates the range [0, 1]
2 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 5 ms 376 KB Integer -1 violates the range [0, 1]
2 Halted 0 ms 0 KB -

Subtask #4
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 5 ms 376 KB Integer -2 violates the range [0, 350000]
2 Halted 0 ms 0 KB -

Subtask #5
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 5 ms 376 KB Integer -2 violates the range [0, 350000]
2 Halted 0 ms 0 KB -

Subtask #6
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 5 ms 504 KB Integer -2 violates the range [0, 350000]
2 Halted 0 ms 0 KB -

Subtask #7
5.0 / 5.0

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

Subtask #8
15.0 / 15.0

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

Subtask #9
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 376 KB Output is correct
2 Correct 5 ms 376 KB Output is correct
3 Correct 5 ms 376 KB Output is correct
4 Correct 5 ms 376 KB Output is correct
5 Correct 5 ms 376 KB Output is correct
6 Correct 5 ms 376 KB Output is correct
7 Correct 5 ms 376 KB Output is correct
8 Correct 5 ms 376 KB Output is correct
9 Correct 44 ms 5616 KB Output is correct
10 Correct 35 ms 4720 KB Output is correct
11 Correct 17 ms 1908 KB Output is correct
12 Correct 19 ms 2424 KB Output is correct
13 Incorrect 9 ms 760 KB Output isn't correct

Subtask #10
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 376 KB Output is correct
2 Correct 5 ms 376 KB Output is correct
3 Correct 5 ms 376 KB Output is correct
4 Correct 5 ms 376 KB Output is correct
5 Correct 5 ms 380 KB Output is correct
6 Correct 5 ms 376 KB Output is correct
7 Correct 5 ms 380 KB Output is correct
8 Correct 5 ms 376 KB Output is correct
9 Correct 43 ms 5744 KB Output is correct
10 Correct 36 ms 4720 KB Output is correct
11 Correct 17 ms 1908 KB Output is correct
12 Correct 19 ms 2416 KB Output is correct
13 Incorrect 9 ms 764 KB Output isn't correct
14 Halted 0 ms 0 KB -