oj.uz

Submission #86974

# Submission time Handle Problem Language Result Execution time Memory
86974 2018-11-29T02:37:36 Z antimirage Gondola (IOI14_gondola) C++17
60 / 100
 90 ms 4988 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 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 *= (to.first - L) * 1ll * sz % mod,
			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 256 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 536 KB Output is correct
4 Correct 3 ms 564 KB Output is correct
5 Correct 2 ms 636 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 636 KB Output is correct
2 Correct 2 ms 636 KB Output is correct
3 Correct 2 ms 636 KB Output is correct
4 Correct 2 ms 636 KB Output is correct
5 Correct 3 ms 636 KB Output is correct
6 Correct 33 ms 2428 KB Output is correct
7 Correct 14 ms 2428 KB Output is correct
8 Correct 56 ms 4300 KB Output is correct
9 Correct 18 ms 4300 KB Output is correct
10 Correct 89 ms 4860 KB Output is correct

Subtask #3
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 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 32 ms 4860 KB Output is correct
7 Correct 14 ms 4860 KB Output is correct
8 Correct 58 ms 4860 KB Output is correct
9 Correct 20 ms 4860 KB Output is correct
10 Correct 90 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 30 ms 4860 KB Output is correct
14 Correct 2 ms 4860 KB Output is correct
15 Correct 55 ms 4988 KB Output is correct

Subtask #4
5.0 / 5.0

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

Subtask #5
10.0 / 10.0

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

Subtask #6
20.0 / 20.0

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

Subtask #7
5.0 / 5.0

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

Subtask #8
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4988 KB Output is correct
2 Correct 2 ms 4988 KB Output is correct
3 Correct 2 ms 4988 KB Output is correct
4 Correct 2 ms 4988 KB Output is correct
5 Incorrect 2 ms 4988 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #9
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4988 KB Output is correct
2 Correct 2 ms 4988 KB Output is correct
3 Correct 2 ms 4988 KB Output is correct
4 Correct 2 ms 4988 KB Output is correct
5 Incorrect 2 ms 4988 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #10
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4988 KB Output is correct
2 Correct 2 ms 4988 KB Output is correct
3 Correct 2 ms 4988 KB Output is correct
4 Correct 2 ms 4988 KB Output is correct
5 Incorrect 2 ms 4988 KB Output isn't correct
6 Halted 0 ms 0 KB -