oj.uz

Submission #86973

# Submission time Handle Problem Language Result Execution time Memory
86973 2018-11-29T02:31:29 Z antimirage Gondola (IOI14_gondola) C++17
80 / 100
 1000 ms 2616 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 u[N], sz, mx, pos, ind[N], ar[N], n, fl;

deque <pair <int, int> > vec;

int valid(int N, int x[])
{
	n = N;
	for (int i = 0; i < n; i++)
	{
		if (x[i] > n) continue;
		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 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) );
	
	sz = 0;
	for (int i = n + 1; i <= mx; i++)
	{
		if ( vec[0].first == i )
			vec.pop_front();
		else
			ans *= (int)vec.size(),
			ans %= mod;
	}
	if (!fl)
		ans *= n, ans %= mod;
	return ans;
}
/**
4
3
3 1 4
**/

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 2 ms 408 KB Output is correct
4 Correct 2 ms 408 KB Output is correct
5 Correct 2 ms 468 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 484 KB Output is correct
2 Correct 2 ms 540 KB Output is correct
3 Correct 2 ms 616 KB Output is correct
4 Correct 2 ms 620 KB Output is correct
5 Correct 2 ms 620 KB Output is correct
6 Correct 7 ms 876 KB Output is correct
7 Correct 14 ms 1260 KB Output is correct
8 Correct 11 ms 1260 KB Output is correct
9 Correct 5 ms 1260 KB Output is correct
10 Correct 14 ms 1276 KB Output is correct

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1276 KB Output is correct
2 Correct 2 ms 1276 KB Output is correct
3 Correct 2 ms 1276 KB Output is correct
4 Correct 2 ms 1276 KB Output is correct
5 Correct 2 ms 1276 KB Output is correct
6 Correct 7 ms 1276 KB Output is correct
7 Correct 16 ms 1276 KB Output is correct
8 Correct 11 ms 1276 KB Output is correct
9 Correct 5 ms 1276 KB Output is correct
10 Correct 14 ms 1288 KB Output is correct
11 Incorrect 2 ms 1288 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #4
5.0 / 5.0

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

Subtask #5
10.0 / 10.0

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

Subtask #6
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1288 KB Output is correct
2 Correct 2 ms 1288 KB Output is correct
3 Correct 2 ms 1288 KB Output is correct
4 Correct 2 ms 1288 KB Output is correct
5 Correct 2 ms 1288 KB Output is correct
6 Correct 2 ms 1288 KB Output is correct
7 Correct 2 ms 1288 KB Output is correct
8 Correct 3 ms 1288 KB Output is correct
9 Correct 3 ms 1288 KB Output is correct
10 Correct 2 ms 1288 KB Output is correct
11 Correct 14 ms 1288 KB Output is correct
12 Correct 20 ms 1324 KB Output is correct
13 Correct 18 ms 1836 KB Output is correct
14 Correct 13 ms 1836 KB Output is correct
15 Correct 24 ms 2616 KB Output is correct

Subtask #7
5.0 / 5.0

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

Subtask #8
15.0 / 15.0

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

Subtask #9
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2616 KB Output is correct
2 Correct 2 ms 2616 KB Output is correct
3 Correct 2 ms 2616 KB Output is correct
4 Correct 2 ms 2616 KB Output is correct
5 Correct 2 ms 2616 KB Output is correct
6 Correct 2 ms 2616 KB Output is correct
7 Correct 2 ms 2616 KB Output is correct
8 Correct 2 ms 2616 KB Output is correct
9 Correct 21 ms 2616 KB Output is correct
10 Correct 18 ms 2616 KB Output is correct
11 Correct 11 ms 2616 KB Output is correct
12 Correct 15 ms 2616 KB Output is correct
13 Correct 6 ms 2616 KB Output is correct

Subtask #10
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2616 KB Output is correct
2 Correct 2 ms 2616 KB Output is correct
3 Correct 2 ms 2616 KB Output is correct
4 Correct 2 ms 2616 KB Output is correct
5 Correct 2 ms 2616 KB Output is correct
6 Correct 2 ms 2616 KB Output is correct
7 Correct 2 ms 2616 KB Output is correct
8 Correct 2 ms 2616 KB Output is correct
9 Correct 22 ms 2616 KB Output is correct
10 Correct 19 ms 2616 KB Output is correct
11 Correct 9 ms 2616 KB Output is correct
12 Correct 10 ms 2616 KB Output is correct
13 Correct 5 ms 2616 KB Output is correct
14 Execution timed out 1075 ms 2616 KB Time limit exceeded
15 Halted 0 ms 0 KB -