oj.uz

Submission #94469

# Submission time Handle Problem Language Result Execution time Memory
94469 2019-01-19T02:09:39 Z fjzzq2002 Gondola (IOI14_gondola) C++14
100 / 100
 105 ms 6904 KB 
#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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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