답안 #86974 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
86974	2018-11-29T02:37:36 Z	antimirage	곤돌라 (IOI14_gondola)	C++17	60 / 100	90 ms	4988 KB

gondola

#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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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	-

답안 #86974

Compilation message