oj.uz

Submission #86977

# Submission time Handle Problem Language Result Execution time Memory
86977 2018-11-29T02:58:02 Z antimirage Gondola (IOI14_gondola) C++17
100 / 100
 120 ms 11532 KB 
#include "gondola.h"
#include <bits/stdc++.h>

#define fr first
#define sc second
#define pb push_back
#define mk make_pair
#define all(s) s.begin(), s.end()

using namespace std;

const int N = 3e5 + 5, mod = 1e9 + 9;

int sz, mx, pos, ind[N], ar[N], n, fl;

deque <pair <int, int> > vec;

map <int, int> u;

int valid(int N, int x[])
{
	n = N;
	for (int i = 0; i < n; i++)
	{
		if (u.count(x[i]))
			return 0;
		u[x[i]] = i + 1;	
	}
	for (int i = 1; i < n; i++)	
	{
		if ( u[i] != 0 && u[i + 1] != 0 && ((u[i] - 1) + 1) % n != u[i + 1] - 1)
			return 0;
	}
	if ( u[n] != 0 && u[1] != 0 && ((u[n] - 1) + 1) % n != u[1] - 1)
		return 0;
		
	return 1;
}	
int replacement(int n, int a[], int ans[])
{
	for (int i = 0; i < n; i++)
		mx = max(a[i], mx);
		
	for (int i = 0; i < n; i++)
	{
		if(a[i] > n)
			vec.pb( mk(a[i], i) );
		else
			pos = (i - (a[i] - 1) + n) % n;
	}
	sort( all(vec) );
	ind[pos] = ++sz;
	
	for (int i = (pos + 1) % n; i != pos; i = (i + 1) % n)
		ind[i] = ++sz;
	
	sz = 0;
	for (int i = n + 1; i <= mx; i++)
	{
		ans[sz++] = ind[ vec[0].second ];
		ind[ vec[0].second ] = i;
		if ( vec[0].first == i )
			vec.pop_front();
	}
	return sz;
}
int binpow (int a, int b)
{
	if (b == 0)
		return 1;
		
	if (b & 1)
		return a * 1ll * binpow(a, b - 1) % mod;
		
	int res = binpow(a , b >> 1);
	
	return res * 1ll * res % mod;
}
int countReplacement(int n, int a[])
{
	long long ans = 1;
	if (valid(n, a) == 0)
		return 0;
		
	for (int i = 0; i < n; i++)
		mx = max(a[i], mx);
		
	for (int i = 0; i < n; i++)
	{
		if(a[i] > n)
			vec.pb( mk(a[i], i) );
		else
			pos = (i - (a[i] - 1) + n) % n, fl = 1;
	}
	sort( all(vec) );
	
	int L = n + 1;
	
	sz = vec.size();
	for (auto to : vec)
	{
		if (to.first != L){
			ans *= binpow( sz, (to.first - L) ),
			ans %= mod;
		}
		L = to.first + 1;
		sz--;
	}
	if (!fl)
		ans *= n, ans %= mod;
		
	return ans;
}
/**
9
4
1 2 7 6
**/

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 472 KB Output is correct
3 Correct 2 ms 472 KB Output is correct
4 Correct 2 ms 488 KB Output is correct
5 Correct 2 ms 488 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 488 KB Output is correct
2 Correct 2 ms 516 KB Output is correct
3 Correct 2 ms 544 KB Output is correct
4 Correct 2 ms 572 KB Output is correct
5 Correct 2 ms 572 KB Output is correct
6 Correct 36 ms 2404 KB Output is correct
7 Correct 19 ms 2404 KB Output is correct
8 Correct 56 ms 4192 KB Output is correct
9 Correct 23 ms 4192 KB Output is correct
10 Correct 102 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 31 ms 4832 KB Output is correct
7 Correct 14 ms 4832 KB Output is correct
8 Correct 56 ms 4832 KB Output is correct
9 Correct 23 ms 4832 KB Output is correct
10 Correct 83 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 28 ms 4860 KB Output is correct
14 Correct 2 ms 4860 KB Output is correct
15 Correct 54 ms 4992 KB Output is correct

Subtask #4
5.0 / 5.0

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

Subtask #5
10.0 / 10.0

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

Subtask #6
20.0 / 20.0

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

Subtask #7
5.0 / 5.0

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

Subtask #8
15.0 / 15.0

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

Subtask #9
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4992 KB Output is correct
2 Correct 2 ms 4992 KB Output is correct
3 Correct 2 ms 4992 KB Output is correct
4 Correct 2 ms 4992 KB Output is correct
5 Correct 2 ms 4992 KB Output is correct
6 Correct 2 ms 4992 KB Output is correct
7 Correct 2 ms 4992 KB Output is correct
8 Correct 2 ms 4992 KB Output is correct
9 Correct 86 ms 7584 KB Output is correct
10 Correct 76 ms 7584 KB Output is correct
11 Correct 32 ms 7584 KB Output is correct
12 Correct 29 ms 7584 KB Output is correct
13 Correct 7 ms 7584 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 7584 KB Output is correct
2 Correct 2 ms 7584 KB Output is correct
3 Correct 2 ms 7584 KB Output is correct
4 Correct 2 ms 7584 KB Output is correct
5 Correct 2 ms 7584 KB Output is correct
6 Correct 2 ms 7584 KB Output is correct
7 Correct 2 ms 7584 KB Output is correct
8 Correct 3 ms 7584 KB Output is correct
9 Correct 79 ms 7584 KB Output is correct
10 Correct 62 ms 7584 KB Output is correct
11 Correct 23 ms 7584 KB Output is correct
12 Correct 27 ms 7584 KB Output is correct
13 Correct 7 ms 7584 KB Output is correct
14 Correct 104 ms 9532 KB Output is correct
15 Correct 120 ms 11532 KB Output is correct
16 Correct 26 ms 11532 KB Output is correct
17 Correct 76 ms 11532 KB Output is correct
18 Correct 52 ms 11532 KB Output is correct