답안 #86973 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
86973	2018-11-29T02:31:29 Z	antimirage	곤돌라 (IOI14_gondola)	C++17	80 / 100	1000 ms	2616 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 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

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

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

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

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

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

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

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

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

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

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

답안 #86973

Compilation message