답안 #94469 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
94469	2019-01-19T02:09:39 Z	fjzzq2002	곤돌라 (IOI14_gondola)	C++14	100 / 100	105 ms	6904 KB

gondola

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

int valid(int n,int x_[])
{
	static int x[100001];
	set<int> u;
	int s=0;
	for(int i=0;i<n;++i)
	{
		x[i]=x_[i]-1; u.insert(x[i]);
		if(x[i]<n) s=(x[i]-i+n)%n;
		if(x[i]<0) return 0;
	}
	if(int(u.size())!=n) return 0;
	for(int i=0;i<n;++i)
		if(x[i]<n&&(s+i)%n!=x[i]) return 0;
	return 1;
}

//----------------------

int replacement(int n, int x_[], int o[])
{
	static int x[100001],y[100001];
	set<int> em;
	map<int,int> t;
	int s=0,mx=0;
	for(int i=0;i<n;++i)
	{
		x[i]=x_[i]-1;
		t[x[i]]=i; mx=max(mx,x[i]);
		if(x[i]<n) s=(x[i]-i+n)%n;
		if(x[i]<0) return 0;
	}
	for(int i=0;i<n;++i)
	{
		y[i]=(s+i)%n;
		if(y[i]!=x[i]) em.insert(i);
	}
	int on=0;
	for(int j=n;j<=mx;++j)
	{
		int p;
		if(t.count(j))
			em.erase(p=t[j]);
		else p=*em.begin();
		o[on++]=y[p]+1; y[p]=j;
	}
	return on;
}

//----------------------

#define fi first
#define se second
const int MOD=1e9+9;
typedef long long ll;
ll qp(ll a,ll b)
{
	ll x=1; a%=MOD;
	while(b)
	{
		if(b&1) x=x*a%MOD;
		a=a*a%MOD; b>>=1;
	}
	return x;
}

int countReplacement(int n, int x_[])
{
	if(!valid(n,x_)) return 0;
	static int x[100001],y[100001];
	map<int,int> sb;
	int s=n,mx=0;
	for(int i=0;i<n;++i)
	{
		x[i]=x_[i]-1; mx=max(mx,x[i]);
		if(x[i]<n) s=(x[i]-i+n)%n;
		if(x[i]<0) return 0;
	}
	for(int i=0;i<n;++i)
	{
		y[i]=(s+i)%n;
		if(y[i]!=x[i]) sb[x[i]]--;
	}
	int ini=sb.size();
	sb[mx+1]=0;
	sb[n-1]+=ini;
	ll ans=1;
	int su=0;
	for(auto t=sb.begin();;++t)
	{
		if(t->fi>mx) break;
		su+=t->se;
		auto u=t; ++u;
		ans=ans*qp(su,u->fi-t->fi-1)%MOD;
	}
	if(s==n) ans=ans*(ll)n%MOD;
	return ans;
}

Subtask #1
5.0 / 5.0

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

Subtask #2
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	376 KB	Output is correct
4	Correct	2 ms	376 KB	Output is correct
5	Correct	2 ms	376 KB	Output is correct
6	Correct	13 ms	2556 KB	Output is correct
7	Correct	33 ms	4472 KB	Output is correct
8	Correct	25 ms	4600 KB	Output is correct
9	Correct	9 ms	1656 KB	Output is correct
10	Correct	32 ms	5368 KB	Output is correct

Subtask #3
10.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	376 KB	Output is correct
2	Correct	2 ms	348 KB	Output is correct
3	Correct	2 ms	256 KB	Output is correct
4	Correct	2 ms	376 KB	Output is correct
5	Correct	2 ms	376 KB	Output is correct
6	Correct	14 ms	2600 KB	Output is correct
7	Correct	34 ms	4472 KB	Output is correct
8	Correct	27 ms	4600 KB	Output is correct
9	Correct	9 ms	1676 KB	Output is correct
10	Correct	38 ms	5332 KB	Output is correct
11	Correct	2 ms	376 KB	Output is correct
12	Correct	2 ms	376 KB	Output is correct
13	Correct	17 ms	2424 KB	Output is correct
14	Correct	2 ms	376 KB	Output is correct
15	Correct	51 ms	5592 KB	Output is correct

Subtask #4
5.0 / 5.0

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

Subtask #5
10.0 / 10.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	380 KB	Output is correct
4	Correct	2 ms	376 KB	Output is correct
5	Correct	2 ms	376 KB	Output is correct
6	Correct	2 ms	376 KB	Output is correct
7	Correct	2 ms	376 KB	Output is correct
8	Correct	2 ms	376 KB	Output is correct
9	Correct	4 ms	376 KB	Output is correct
10	Correct	4 ms	376 KB	Output is correct

Subtask #6
20.0 / 20.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	376 KB	Output is correct
4	Correct	2 ms	380 KB	Output is correct
5	Correct	2 ms	376 KB	Output is correct
6	Correct	2 ms	376 KB	Output is correct
7	Correct	2 ms	376 KB	Output is correct
8	Correct	2 ms	376 KB	Output is correct
9	Correct	2 ms	376 KB	Output is correct
10	Correct	2 ms	376 KB	Output is correct
11	Correct	29 ms	5368 KB	Output is correct
12	Correct	35 ms	6044 KB	Output is correct
13	Correct	46 ms	4728 KB	Output is correct
14	Correct	32 ms	5412 KB	Output is correct
15	Correct	36 ms	3964 KB	Output is correct

Subtask #7
5.0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	252 KB	Output is correct
2	Correct	2 ms	376 KB	Output is correct
3	Correct	2 ms	376 KB	Output is correct

Subtask #8
15.0 / 15.0

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

Subtask #9
15.0 / 15.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	376 KB	Output is correct
4	Correct	2 ms	376 KB	Output is correct
5	Correct	2 ms	376 KB	Output is correct
6	Correct	2 ms	376 KB	Output is correct
7	Correct	2 ms	376 KB	Output is correct
8	Correct	2 ms	376 KB	Output is correct
9	Correct	66 ms	5112 KB	Output is correct
10	Correct	57 ms	4216 KB	Output is correct
11	Correct	19 ms	1784 KB	Output is correct
12	Correct	22 ms	2040 KB	Output is correct
13	Correct	6 ms	760 KB	Output is correct

Subtask #10
10.0 / 10.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	376 KB	Output is correct
4	Correct	2 ms	376 KB	Output is correct
5	Correct	2 ms	376 KB	Output is correct
6	Correct	2 ms	376 KB	Output is correct
7	Correct	2 ms	376 KB	Output is correct
8	Correct	2 ms	380 KB	Output is correct
9	Correct	70 ms	5112 KB	Output is correct
10	Correct	49 ms	4344 KB	Output is correct
11	Correct	20 ms	1784 KB	Output is correct
12	Correct	23 ms	2168 KB	Output is correct
13	Correct	6 ms	768 KB	Output is correct
14	Correct	91 ms	6008 KB	Output is correct
15	Correct	105 ms	6904 KB	Output is correct
16	Correct	14 ms	1528 KB	Output is correct
17	Correct	64 ms	4728 KB	Output is correct
18	Correct	35 ms	2808 KB	Output is correct

답안 #94469

Compilation message