oj.uz

Submission #200785

# Submission time Handle Problem Language Result Execution time Memory
200785 2020-02-08T06:53:07 Z mohammad Gondola (IOI14_gondola) C++14
20 / 100
 44 ms 6132 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 += ans1;
	}
	return ans ;
}

Subtask #1
0 / 5.0

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

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

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

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

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 380 KB Integer -2 violates the range [0, 350000]
2 Halted 0 ms 0 KB -

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 376 KB Integer -2 violates the range [0, 350000]
2 Halted 0 ms 0 KB -

Subtask #7
5.0 / 5.0

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

Subtask #8
15.0 / 15.0

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

# Verdict Execution time Memory 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 6132 KB Output is correct
10 Correct 36 ms 5104 KB Output is correct
11 Correct 17 ms 2036 KB Output is correct
12 Correct 20 ms 2548 KB Output is correct
13 Incorrect 10 ms 888 KB Output isn't correct

Subtask #10
0 / 10.0

# Verdict Execution time Memory 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 504 KB Output is correct
7 Correct 5 ms 376 KB Output is correct
8 Correct 5 ms 376 KB Output is correct
9 Correct 43 ms 6128 KB Output is correct
10 Correct 38 ms 5100 KB Output is correct
11 Correct 17 ms 2012 KB Output is correct
12 Correct 23 ms 2548 KB Output is correct
13 Incorrect 9 ms 760 KB Output isn't correct
14 Halted 0 ms 0 KB -