답안 #611015

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
611015	2022-07-29T00:49:22 Z	penguinhacker	곤돌라 (IOI14_gondola)	C++17	100 / 100	29 ms	2228 KB

gondola

#include <bits/stdc++.h>
#include "gondola.h"
using namespace std;

void rot(vector<int>& a) {
	int n=a.size();
	for (int i=0; i<n; ++i)
		if (a[i]<=n) {
			int st=(i-(a[i]-1)+n)%n;
			rotate(a.begin(), a.begin()+st, a.end());
			break;
		}
}

int valid(int n, vector<int> a) {
	vector<int> b=a;
	sort(b.begin(), b.end());
	for (int i=0; i+1<n; ++i)
		if (b[i]==b[i+1])
			return 0;
	if (*min_element(a.begin(), a.end())>n)
		return 1;
	rot(a);
	for (int i=0; i<n; ++i)
		if (a[i]<=n&&a[i]!=i+1)
			return 0;
	return 1;
}

int valid(int n, int a[]) {
	return valid(n, vector<int>(a, a+n));
}

int replacement(int n, vector<int> a, int b[]) {
	assert(valid(n, a));
	rot(a);
	int mx=*max_element(a.begin(), a.end());
	vector<int> who(mx+1, -1);
	for (int i=0; i<n; ++i)
		who[a[i]]=i;
	vector<int> seq(n);
	iota(seq.begin(), seq.end(), 1);
	for (int i=n+1; i<=mx; ++i) {
		int pos=who[i]!=-1?who[i]:who[mx];
		b[i-n-1]=seq[pos];
		seq[pos]=i;
	}
	return mx-n;
}

int replacement(int n, int a[], int b[]) {
	return replacement(n, vector<int>(a, a+n), b);
}

const int M=1e9+9;

#define ll long long

ll bp(ll b, int p) {
	ll r=1;
	for (; p; p/=2, b=b*b%M)
		if (p%2)
			r=r*b%M;
	return r;
}

int countReplacement(int n, vector<int> a) {
	if (!valid(n, a))
		return 0;
	rot(a);
	int free=0;
	vector<int> pos;
	for (int i : a) {
		if (i>n) {
			++free;
			pos.push_back(i);
		}
	}
	sort(pos.begin(), pos.end());
	int last=n;
	ll ans=1;
	for (int i : pos) {
		ans=ans*bp(free--, i-last-1)%M;
		last=i;
	}
	if (*min_element(a.begin(), a.end())>n)
		ans=ans*n%M;
	return ans;
}

int countReplacement(int n, int a[]) {
	return countReplacement(n, vector<int>(a, a+n));
}

Subtask #1
5.0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	212 KB	Output is correct
2	Correct	1 ms	212 KB	Output is correct
3	Correct	0 ms	212 KB	Output is correct
4	Correct	0 ms	212 KB	Output is correct
5	Correct	1 ms	212 KB	Output is correct

Subtask #2
5.0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	212 KB	Output is correct
2	Correct	0 ms	212 KB	Output is correct
3	Correct	0 ms	212 KB	Output is correct
4	Correct	0 ms	212 KB	Output is correct
5	Correct	0 ms	212 KB	Output is correct
6	Correct	6 ms	724 KB	Output is correct
7	Correct	13 ms	1236 KB	Output is correct
8	Correct	9 ms	1112 KB	Output is correct
9	Correct	4 ms	468 KB	Output is correct
10	Correct	20 ms	1300 KB	Output is correct

Subtask #3
10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	212 KB	Output is correct
2	Correct	0 ms	212 KB	Output is correct
3	Correct	0 ms	292 KB	Output is correct
4	Correct	0 ms	212 KB	Output is correct
5	Correct	0 ms	212 KB	Output is correct
6	Correct	6 ms	724 KB	Output is correct
7	Correct	12 ms	1236 KB	Output is correct
8	Correct	11 ms	1108 KB	Output is correct
9	Correct	4 ms	468 KB	Output is correct
10	Correct	14 ms	1204 KB	Output is correct
11	Correct	1 ms	212 KB	Output is correct
12	Correct	1 ms	212 KB	Output is correct
13	Correct	5 ms	724 KB	Output is correct
14	Correct	1 ms	212 KB	Output is correct
15	Correct	15 ms	1768 KB	Output is correct

Subtask #4
5.0 / 5.0

#	결과	메모리	Grader output
1	Correct	212 KB	Output is correct
2	Correct	212 KB	Output is correct
3	Correct	212 KB	Output is correct
4	Correct	212 KB	Output is correct
5	Correct	212 KB	Output is correct

Subtask #5
10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	212 KB	Output is correct
2	Correct	0 ms	212 KB	Output is correct
3	Correct	0 ms	212 KB	Output is correct
4	Correct	0 ms	212 KB	Output is correct
5	Correct	0 ms	212 KB	Output is correct
6	Correct	0 ms	212 KB	Output is correct
7	Correct	1 ms	212 KB	Output is correct
8	Correct	1 ms	340 KB	Output is correct
9	Correct	1 ms	340 KB	Output is correct
10	Correct	1 ms	340 KB	Output is correct

Subtask #6
20.0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	212 KB	Output is correct
2	Correct	0 ms	212 KB	Output is correct
3	Correct	0 ms	212 KB	Output is correct
4	Correct	0 ms	212 KB	Output is correct
5	Correct	0 ms	212 KB	Output is correct
6	Correct	0 ms	212 KB	Output is correct
7	Correct	0 ms	212 KB	Output is correct
8	Correct	1 ms	340 KB	Output is correct
9	Correct	1 ms	340 KB	Output is correct
10	Correct	1 ms	340 KB	Output is correct
11	Correct	9 ms	1492 KB	Output is correct
12	Correct	11 ms	1688 KB	Output is correct
13	Correct	15 ms	1348 KB	Output is correct
14	Correct	10 ms	1536 KB	Output is correct
15	Correct	21 ms	2228 KB	Output is correct

Subtask #7
5.0 / 5.0

#	결과	메모리	Grader output
1	Correct	212 KB	Output is correct
2	Correct	212 KB	Output is correct
3	Correct	212 KB	Output is correct

Subtask #8
15.0 / 15.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	212 KB	Output is correct
2	Correct	0 ms	212 KB	Output is correct
3	Correct	0 ms	212 KB	Output is correct
4	Correct	0 ms	212 KB	Output is correct
5	Correct	0 ms	212 KB	Output is correct
6	Correct	0 ms	212 KB	Output is correct
7	Correct	0 ms	212 KB	Output is correct
8	Correct	1 ms	212 KB	Output is correct

Subtask #9
15.0 / 15.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	224 KB	Output is correct
2	Correct	1 ms	212 KB	Output is correct
3	Correct	0 ms	212 KB	Output is correct
4	Correct	0 ms	212 KB	Output is correct
5	Correct	0 ms	212 KB	Output is correct
6	Correct	0 ms	212 KB	Output is correct
7	Correct	0 ms	212 KB	Output is correct
8	Correct	0 ms	212 KB	Output is correct
9	Correct	16 ms	1352 KB	Output is correct
10	Correct	14 ms	1236 KB	Output is correct
11	Correct	5 ms	680 KB	Output is correct
12	Correct	7 ms	724 KB	Output is correct
13	Correct	2 ms	340 KB	Output is correct

Subtask #10
10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	212 KB	Output is correct
2	Correct	1 ms	212 KB	Output is correct
3	Correct	0 ms	212 KB	Output is correct
4	Correct	0 ms	212 KB	Output is correct
5	Correct	0 ms	212 KB	Output is correct
6	Correct	1 ms	212 KB	Output is correct
7	Correct	0 ms	212 KB	Output is correct
8	Correct	0 ms	212 KB	Output is correct
9	Correct	24 ms	1472 KB	Output is correct
10	Correct	13 ms	1236 KB	Output is correct
11	Correct	5 ms	680 KB	Output is correct
12	Correct	6 ms	724 KB	Output is correct
13	Correct	2 ms	340 KB	Output is correct
14	Correct	21 ms	1732 KB	Output is correct
15	Correct	29 ms	1924 KB	Output is correct
16	Correct	7 ms	588 KB	Output is correct
17	Correct	21 ms	1236 KB	Output is correct
18	Correct	12 ms	896 KB	Output is correct

답안 #611015

Compilation message