oj.uz

Submission #417746

# Submission time Handle Problem Language Result Execution time Memory
417746 2021-06-04T08:27:16 Z vanic Gondola (IOI14_gondola) C++14
100 / 100
 87 ms 6308 KB 
#include "gondola.h"
#include <cmath>
#include <algorithm>
#include <vector>
#include <map>
#include <cassert>
#include <iostream>

using namespace std;

typedef long long ll;

const int maxn=1e5+5, mod=1e9+9, Log=30;

inline int sum(int a, int b){
	if(a+b>=mod){
		return a+b-mod;
	}
	if(a+b<0){
		return a+b+mod;
	}
	return a+b;
}

inline int mul(int a, int b){
	return (ll)a*b%mod;
}

inline int pot(int a, int b){
	int sol=1;
	for(int i=0; i<Log; i++){
		if((1<<i)&b){
			sol=mul(sol, a);
		}
		a=mul(a, a);
	}
	return sol;
}

int poc[maxn];
map < int, int > bio;

int valid(int n, int l[]){
	for(int i=0; i<n; i++){
		if(bio[l[i]]){
			return 0;
		}
		bio[l[i]]=1;
		poc[i]=i+1;
	}
	bio.clear();
	int pos=-1;
	for(int i=0; i<n; i++){
		if(l[i]<=n){
			pos=i;
			break;
		}
	}
	if(pos==-1){
		return 1;
	}
	int val=l[pos];
	for(int i=0; i<n; i++){
		poc[pos]=val;
		val=(val+1)%n;
		pos=(pos+1)%n;
		if(!val){
			val=n;
		}
	}
	for(int i=0; i<n; i++){
		if(l[i]<=n && poc[i]!=l[i]){
			return 0;
		}
	}
	return 1;
}



int replacement(int n, int l[], int sol[]){
	assert(valid(n, l));
	int maksi=0, ind;
	for(int i=0; i<n; i++){
		bio[l[i]]=i;
		if(maksi<l[i]){
			maksi=l[i];
			ind=i;
		}
	}
	int pos=0;
	for(int i=n+1; i<=maksi; i++){
		if(bio.find(i)!=bio.end()){
			sol[pos]=poc[bio[i]];
			poc[bio[i]]=i;
		}
		else{
			sol[pos]=poc[ind];
			poc[ind]=i;
		}
		pos++;
	}
	bio.clear();
	return maksi-n;
}

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

int countReplacement(int n, int l[]){
	if(!valid(n, l)){
		return 0;
	}
	bool nema=1;
	for(int i=0; i<n; i++){
		if(l[i]<=n){
			nema=0;
			break;
		}
	}
	sort(l, l+n);
	vector < int > v;
	v.push_back(n);
	int p=-1;
	for(int i=0; i<n; i++){
		if(l[i]>n){
			if(p==-1){
				p=n-i;
			}
			v.push_back(l[i]);
		}
	}
	int sol=1;
	for(int i=0; i<(int)v.size()-1; i++){
		sol=mul(sol, pot(p, v[i+1]-v[i]-1));
		p--;
	}
	if(nema){
		sol=mul(sol, n);
	}
	return sol;
}

Compilation message

gondola.cpp: In function 'int replacement(int, int*, int*)':
gondola.cpp:98:20: warning: 'ind' may be used uninitialized in this function [-Wmaybe-uninitialized]
   98 |    sol[pos]=poc[ind];
      |             ~~~~~~~^

Subtask #1
5.0 / 5.0

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

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 224 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 0 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 0 ms 204 KB Output is correct
6 Correct 15 ms 2252 KB Output is correct
7 Correct 10 ms 588 KB Output is correct
8 Correct 31 ms 4112 KB Output is correct
9 Correct 9 ms 1484 KB Output is correct
10 Correct 36 ms 4740 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 0 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 16 ms 2368 KB Output is correct
7 Correct 10 ms 652 KB Output is correct
8 Correct 32 ms 4172 KB Output is correct
9 Correct 11 ms 1484 KB Output is correct
10 Correct 36 ms 4804 KB Output is correct
11 Correct 0 ms 204 KB Output is correct
12 Correct 0 ms 204 KB Output is correct
13 Correct 19 ms 2116 KB Output is correct
14 Correct 0 ms 204 KB Output is correct
15 Correct 50 ms 4924 KB Output is correct

Subtask #4
5.0 / 5.0

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

Subtask #5
10.0 / 10.0

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

Subtask #6
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 0 ms 204 KB Output is correct
6 Correct 0 ms 204 KB Output is correct
7 Correct 2 ms 332 KB Output is correct
8 Correct 1 ms 332 KB Output is correct
9 Correct 1 ms 332 KB Output is correct
10 Correct 2 ms 332 KB Output is correct
11 Correct 56 ms 4608 KB Output is correct
12 Correct 59 ms 5120 KB Output is correct
13 Correct 45 ms 2756 KB Output is correct
14 Correct 46 ms 4548 KB Output is correct
15 Correct 38 ms 2840 KB Output is correct

Subtask #7
5.0 / 5.0

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

Subtask #8
15.0 / 15.0

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

Subtask #9
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 0 ms 204 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 1 ms 204 KB Output is correct
7 Correct 0 ms 204 KB Output is correct
8 Correct 0 ms 204 KB Output is correct
9 Correct 63 ms 4308 KB Output is correct
10 Correct 46 ms 3524 KB Output is correct
11 Correct 19 ms 1524 KB Output is correct
12 Correct 22 ms 1764 KB Output is correct
13 Correct 5 ms 640 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 0 ms 204 KB Output is correct
4 Correct 0 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 1 ms 204 KB Output is correct
7 Correct 0 ms 204 KB Output is correct
8 Correct 1 ms 204 KB Output is correct
9 Correct 61 ms 4280 KB Output is correct
10 Correct 46 ms 3524 KB Output is correct
11 Correct 17 ms 1516 KB Output is correct
12 Correct 22 ms 1696 KB Output is correct
13 Correct 6 ms 588 KB Output is correct
14 Correct 73 ms 5608 KB Output is correct
15 Correct 87 ms 6308 KB Output is correct
16 Correct 13 ms 1356 KB Output is correct
17 Correct 54 ms 4336 KB Output is correct
18 Correct 29 ms 2484 KB Output is correct