oj.uz

Submission #48999

# Submission time Handle Problem Language Result Execution time Memory
48999 2018-05-21T06:27:57 Z Namnamseo Gondola (IOI14_gondola) C++17
100 / 100
 111 ms 16676 KB 
#include "gondola.h"
#include <bits/stdc++.h>
using namespace std;

int valid(int n, int a[])
{
	set<int> jb;
	set<int> of;
	for(int i=0; i<n; ++i){
		if(jb.find(a[i]) != jb.end()) return 0;
		jb.insert(a[i]);
		if(1<=a[i] && a[i]<=n){
			int t=(a[i]-i+n)%n;
			of.insert(t);
		}
	}
	return of.size() <= 1u;
}

//----------------------
#include <algorithm>
#include <cstdio>

int replacement(int n, int gond[], int rep[])
{
	int arr[100010];
	int Mx = 0, Mxp;
	set<int> of;
	for(int i=0; i<n; ++i){
		arr[i] = gond[i];
		if(1<=arr[i] && arr[i]<=n){
			int t=(arr[i]-1-i+2*n)%n;
			of.insert(t);
		}
	}
	
	if(of.size() == 1u){
		int t=*of.begin();
		rotate(arr, arr+n-t, arr+n);
	}
	for(int i=0; i<n; ++i){
		if(Mx < arr[i])
			Mx = arr[i], Mxp=i;
	}
	int mp[250010];
	for(int i=n+1; i<=Mx; ++i)
		mp[i] = -1;
	for(int i=0; i<n; ++i){
		if(arr[i] > n)
			mp[arr[i]] = i;
		arr[i] = i+1;
	}

	for(int i=n+1; i<=Mx; ++i){
		if(mp[i] == -1){
			rep[i-n-1] = arr[Mxp];
			arr[Mxp] = i;
		} else {
			rep[i-n-1] = arr[mp[i]];
		}
	}
	return Mx-n;
}

//----------------------
#define ll long long
#define M (1000000009)
static ll poW(ll a,ll b){
	if(b==0) return 1;
	ll ret=poW(a,b/2);
	ret = ret * ret % M;
	if(b&1)
		ret = ret * a % M;
	return ret;
}

int countReplacement(int n, int gond[])
{
	if(!valid(n, gond)) return 0;

	ll ans = 1;

	vector<int> v;
	for(int i=0; i<n; ++i) if(gond[i] > n) v.push_back(gond[i]);

	sort(v.begin(), v.end());

	int last = n;
	int usa = v.size();

	for(int p:v){
		ans *= poW(usa, p-last-1);
		ans %= M;
		last=p;
		--usa;
	}

	if(v.size() == n){
		ans *= n; ans %= M;
	}

	return ans;
}

Compilation message

gondola.cpp: In function 'int countReplacement(int, int*)':
gondola.cpp:98:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  if(v.size() == n){
     ~~~~~~~~~^~~~
gondola.cpp: In function 'int replacement(int, int*, int*)':
gondola.cpp:57:13: warning: 'Mxp' may be used uninitialized in this function [-Wmaybe-uninitialized]
    arr[Mxp] = i;
    ~~~~~~~~~^~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 504 KB Output is correct
2 Correct 3 ms 628 KB Output is correct
3 Correct 3 ms 636 KB Output is correct
4 Correct 2 ms 636 KB Output is correct
5 Correct 2 ms 636 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 728 KB Output is correct
2 Correct 2 ms 732 KB Output is correct
3 Correct 2 ms 732 KB Output is correct
4 Correct 3 ms 804 KB Output is correct
5 Correct 3 ms 808 KB Output is correct
6 Correct 21 ms 2948 KB Output is correct
7 Correct 17 ms 2948 KB Output is correct
8 Correct 38 ms 5676 KB Output is correct
9 Correct 12 ms 5676 KB Output is correct
10 Correct 56 ms 6880 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 6880 KB Output is correct
2 Correct 2 ms 6880 KB Output is correct
3 Correct 2 ms 6880 KB Output is correct
4 Correct 2 ms 6880 KB Output is correct
5 Correct 3 ms 6880 KB Output is correct
6 Correct 22 ms 6880 KB Output is correct
7 Correct 24 ms 6880 KB Output is correct
8 Correct 39 ms 7604 KB Output is correct
9 Correct 13 ms 7604 KB Output is correct
10 Correct 51 ms 8776 KB Output is correct
11 Correct 2 ms 8776 KB Output is correct
12 Correct 2 ms 8776 KB Output is correct
13 Correct 27 ms 8776 KB Output is correct
14 Correct 2 ms 8776 KB Output is correct
15 Correct 111 ms 11300 KB Output is correct

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 11300 KB Output is correct
2 Correct 2 ms 11300 KB Output is correct
3 Correct 2 ms 11300 KB Output is correct
4 Correct 3 ms 11300 KB Output is correct
5 Correct 2 ms 11300 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 11300 KB Output is correct
2 Correct 3 ms 11300 KB Output is correct
3 Correct 2 ms 11300 KB Output is correct
4 Correct 2 ms 11300 KB Output is correct
5 Correct 2 ms 11300 KB Output is correct
6 Correct 2 ms 11300 KB Output is correct
7 Correct 3 ms 11300 KB Output is correct
8 Correct 3 ms 11300 KB Output is correct
9 Correct 3 ms 11300 KB Output is correct
10 Correct 2 ms 11300 KB Output is correct

Subtask #6
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 11300 KB Output is correct
2 Correct 2 ms 11300 KB Output is correct
3 Correct 2 ms 11300 KB Output is correct
4 Correct 2 ms 11300 KB Output is correct
5 Correct 2 ms 11300 KB Output is correct
6 Correct 2 ms 11300 KB Output is correct
7 Correct 2 ms 11300 KB Output is correct
8 Correct 3 ms 11300 KB Output is correct
9 Correct 2 ms 11300 KB Output is correct
10 Correct 5 ms 11300 KB Output is correct
11 Correct 16 ms 11300 KB Output is correct
12 Correct 17 ms 11300 KB Output is correct
13 Correct 15 ms 11300 KB Output is correct
14 Correct 15 ms 11300 KB Output is correct
15 Correct 25 ms 11300 KB Output is correct

Subtask #7
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 11300 KB Output is correct
2 Correct 2 ms 11300 KB Output is correct
3 Correct 2 ms 11300 KB Output is correct

Subtask #8
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 11300 KB Output is correct
2 Correct 3 ms 11300 KB Output is correct
3 Correct 3 ms 11300 KB Output is correct
4 Correct 2 ms 11300 KB Output is correct
5 Correct 2 ms 11300 KB Output is correct
6 Correct 2 ms 11300 KB Output is correct
7 Correct 2 ms 11300 KB Output is correct
8 Correct 3 ms 11300 KB Output is correct

Subtask #9
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 11300 KB Output is correct
2 Correct 2 ms 11300 KB Output is correct
3 Correct 3 ms 11300 KB Output is correct
4 Correct 3 ms 11300 KB Output is correct
5 Correct 2 ms 11300 KB Output is correct
6 Correct 3 ms 11300 KB Output is correct
7 Correct 2 ms 11300 KB Output is correct
8 Correct 2 ms 11300 KB Output is correct
9 Correct 69 ms 11628 KB Output is correct
10 Correct 55 ms 11628 KB Output is correct
11 Correct 22 ms 11628 KB Output is correct
12 Correct 24 ms 11628 KB Output is correct
13 Correct 7 ms 11628 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 11628 KB Output is correct
2 Correct 2 ms 11628 KB Output is correct
3 Correct 3 ms 11628 KB Output is correct
4 Correct 3 ms 11628 KB Output is correct
5 Correct 2 ms 11628 KB Output is correct
6 Correct 2 ms 11628 KB Output is correct
7 Correct 2 ms 11628 KB Output is correct
8 Correct 2 ms 11628 KB Output is correct
9 Correct 68 ms 13068 KB Output is correct
10 Correct 56 ms 13068 KB Output is correct
11 Correct 17 ms 13068 KB Output is correct
12 Correct 21 ms 13068 KB Output is correct
13 Correct 6 ms 13068 KB Output is correct
14 Correct 88 ms 15320 KB Output is correct
15 Correct 102 ms 16676 KB Output is correct
16 Correct 17 ms 16676 KB Output is correct
17 Correct 64 ms 16676 KB Output is correct
18 Correct 33 ms 16676 KB Output is correct