oj.uz

Submission #155071

# Submission time Handle Problem Language Result Execution time Memory
155071 2019-09-26T06:21:51 Z junodeveloper Gondola (IOI14_gondola) C++14
100 / 100
 88 ms 6008 KB 
#include "gondola.h"
#include <bits/stdc++.h>
#define all(x) (x).begin(),(x).end()
#define sz(x) (int)x.size()
#define fi first
#define se second
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int mod=1e9+9;

int valid(int n, int inputSeq[]) {
	int i;
	set<int> chk;
	for(i=0;i<n;i++) {
		if(chk.count(inputSeq[i])) return 0;
		chk.insert(inputSeq[i]);
	}
	int p=-1,t;
	for(i=0;i<n;i++) {
		if(inputSeq[i]<=n) {
			t=(i-inputSeq[i]+1+n)%n;
			if(p!=-1&&t!=p) return 0;
			p=t;
		}
	}
	return 1;
}

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

int replacement(int n, int gondolaSeq[], int replacementSeq[]) {
	int i,j,p=0;
	for(i=0;i<n;i++) {
		if(gondolaSeq[i]<=n) {
			p=(i-gondolaSeq[i]+1+n)%n;
			break;
		}
	}
	vector<pii> v;
	for(i=0;i<n;i++) {
		if(gondolaSeq[i]>n) {
			v.push_back(make_pair(gondolaSeq[i],i));
		}
	}
	sort(all(v));
	int cur=n,top=0;
	for(i=0;i<sz(v);i++) {
		if(v[i].se>=p) j=v[i].se-p+1;
		else j=n-p+v[i].se+1;
		replacementSeq[top++]=j;cur++;
		while(cur<v[i].fi) replacementSeq[top++]=cur++;
	}
	return top;
}

//----------------------
int modpow(int a,int n) {
	int r=1,b=a;
	while(n>0) {
		if(n&1) r=(ll)r*b%mod;
		b=(ll)b*b%mod;
		n>>=1;
	}
	return r;
}
int countReplacement(int n, int inputSeq[]) {
	if(!valid(n,inputSeq)) return 0;
	vector<int> v;
	int i;
	for(i=0;i<n;i++) {
		if(inputSeq[i]>n) v.push_back(inputSeq[i]);
	}
	if(v.empty()) return 1;
	v.push_back(n);
	sort(all(v));
	int res=1;
	for(i=0;i+1<sz(v);i++) {
		res=(ll)res*modpow(sz(v)-i-1,v[i+1]-v[i]-1)%mod;
	}
	if(sz(v)==n+1) {
		res=(ll)res*n%mod;
	}
	return res;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 252 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 252 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 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 19 ms 2424 KB Output is correct
7 Correct 13 ms 1144 KB Output is correct
8 Correct 34 ms 4320 KB Output is correct
9 Correct 11 ms 1656 KB Output is correct
10 Correct 46 ms 5112 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 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 376 KB Output is correct
5 Correct 2 ms 376 KB Output is correct
6 Correct 19 ms 2428 KB Output is correct
7 Correct 14 ms 1144 KB Output is correct
8 Correct 34 ms 4332 KB Output is correct
9 Correct 11 ms 1656 KB Output is correct
10 Correct 46 ms 5112 KB Output is correct
11 Correct 2 ms 256 KB Output is correct
12 Correct 2 ms 376 KB Output is correct
13 Correct 24 ms 2296 KB Output is correct
14 Correct 2 ms 256 KB Output is correct
15 Correct 57 ms 5216 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 256 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 252 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 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 2 ms 376 KB Output is correct
10 Correct 2 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 256 KB Output is correct
5 Correct 2 ms 380 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 11 ms 1016 KB Output is correct
12 Correct 13 ms 1272 KB Output is correct
13 Correct 17 ms 1532 KB Output is correct
14 Correct 11 ms 1016 KB Output is correct
15 Correct 23 ms 2404 KB Output is correct

Subtask #7
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 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 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 2 ms 376 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 2 ms 256 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 504 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 256 KB Output is correct
8 Correct 2 ms 376 KB Output is correct
9 Correct 56 ms 4604 KB Output is correct
10 Correct 45 ms 3832 KB Output is correct
11 Correct 18 ms 1528 KB Output is correct
12 Correct 21 ms 1912 KB Output is correct
13 Correct 6 ms 632 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 352 KB Output is correct
4 Correct 2 ms 256 KB Output is correct
5 Correct 2 ms 256 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 2 ms 364 KB Output is correct
8 Correct 2 ms 400 KB Output is correct
9 Correct 57 ms 4600 KB Output is correct
10 Correct 46 ms 3832 KB Output is correct
11 Correct 17 ms 1656 KB Output is correct
12 Correct 21 ms 1916 KB Output is correct
13 Correct 6 ms 760 KB Output is correct
14 Correct 72 ms 5432 KB Output is correct
15 Correct 88 ms 6008 KB Output is correct
16 Correct 14 ms 1404 KB Output is correct
17 Correct 53 ms 4188 KB Output is correct
18 Correct 28 ms 2552 KB Output is correct