oj.uz

Submission #50295

# Submission time Handle Problem Language Result Execution time Memory
50295 2018-06-09T16:05:30 Z faishol27 Gondola (IOI14_gondola) C++14
100 / 100
 104 ms 17284 KB 
#include <bits/stdc++.h>
#include "gondola.h"
using namespace std;

typedef long long ll;
typedef pair<int, int> pi;

#define fi first
#define se second
#define PUB push_back

set<int>ada;

int valid(int n, int inputSeq[])
{	
	int isValid;
	int ind_min;

	ada.clear();

	isValid = 1; ind_min = 0;

	for(int i=0;i<n;i++){
		if(inputSeq[i] < inputSeq[ind_min]) ind_min = i;
		if(ada.find(inputSeq[i]) != ada.end()){
			isValid = 0;
		}

		ada.insert(inputSeq[i]);
	}
	
	int str = ind_min,
		fin = ind_min-1,
		cnt = inputSeq[ind_min];

	if(fin<0) fin = n-1;
	//cerr << str << " " << fin << " " << cnt << endl;
	while(str != fin){
		if(inputSeq[str] <= n && inputSeq[str] != cnt){
			isValid = 0;
			break;
		}

		str++; cnt++;
		if(str>=n) str = 0;
	}
	
	return isValid;
}

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

bool cmp1(pi a, pi b){
	return a.fi < b.fi;
}

int replacement(int n, int gondolaSeq[], int replacementSeq[])
{
	int ret=0,
		ind=0,
		tmp=0,
		cnt_chg=n+1,
		cnt = 1,
		nmr = 0;

	vector<pi>data;

	for(int i=0;i<n;i++){
		if(gondolaSeq[i] < gondolaSeq[ind]) ind = i;	
	}

	if(gondolaSeq[ind] <= n){
		ind = ind-gondolaSeq[ind]+1;
		if(ind < 0) ind += n;
	}
	
	while(cnt <= n){
		if(gondolaSeq[ind]>n) data.PUB({gondolaSeq[ind],cnt});
		
		ind++; cnt++;
		if(ind>=n) ind = 0;
	}

	sort(data.begin(), data.end(), cmp1);

	for(int i=0;i<data.size();i++){
		while(data[i].se != data[i].fi){
			replacementSeq[nmr] = data[i].se;
			
			data[i].se = cnt_chg;

			cnt_chg++;
			nmr++;
		}
	}

	ret = nmr;
	return ret;
}

//----------------------
const int MOD = 1e9+9;
int modexp(int bwh, int pgk){
	ll 	b = bwh,
		e = pgk;

	ll r = 1;
	while(e>0){
		if(e&1) r = r*b%MOD;

		e>>=1;
		b = b*b%MOD;
	}
	
	r %= MOD;

	return (int) r;
}

int countReplacement(int n, int inputSeq[])
{
	ll ret=1;
	int cnt=n+1;
	vector<int>data;

	if(valid(n,inputSeq)==0) return 0;

	for(int i=0;i<n;i++){
		if(inputSeq[i] > n) data.PUB(inputSeq[i]);
	}

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

	if(data.size()==n) ret *= n;

	for(int i=0;i<data.size();i++){
		//cerr << (data.size()-i) <<" " << (data[i]-cnt) << " " << modexp((data.size()-i),(data[i]-cnt),MOD) << endl; 
		//cerr << i << " " << ret << endl;
		
		if(data[i]-cnt > 0)
			ret = ret*modexp((data.size()-i),(data[i]-cnt))%MOD;
	
		cnt = data[i]+1;
	}

	ret %= MOD;
	
	return (int) ret;
}

Compilation message

gondola.cpp: In function 'int replacement(int, int*, int*)':
gondola.cpp:86:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<data.size();i++){
              ~^~~~~~~~~~~~
gondola.cpp:61:3: warning: unused variable 'tmp' [-Wunused-variable]
   tmp=0,
   ^~~
gondola.cpp: In function 'int countReplacement(int, int*)':
gondola.cpp:134:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  if(data.size()==n) ret *= n;
     ~~~~~~~~~~~^~~
gondola.cpp:136:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<data.size();i++){
              ~^~~~~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 33 ms 252 KB Output is correct
2 Correct 3 ms 488 KB Output is correct
3 Correct 3 ms 488 KB Output is correct
4 Correct 3 ms 656 KB Output is correct
5 Correct 3 ms 656 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 664 KB Output is correct
2 Correct 2 ms 664 KB Output is correct
3 Correct 2 ms 696 KB Output is correct
4 Correct 3 ms 700 KB Output is correct
5 Correct 2 ms 704 KB Output is correct
6 Correct 21 ms 2800 KB Output is correct
7 Correct 50 ms 4936 KB Output is correct
8 Correct 36 ms 5428 KB Output is correct
9 Correct 12 ms 5428 KB Output is correct
10 Correct 61 ms 6676 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 6676 KB Output is correct
2 Correct 3 ms 6676 KB Output is correct
3 Correct 2 ms 6676 KB Output is correct
4 Correct 2 ms 6676 KB Output is correct
5 Correct 3 ms 6676 KB Output is correct
6 Correct 22 ms 6676 KB Output is correct
7 Correct 51 ms 6840 KB Output is correct
8 Correct 34 ms 7344 KB Output is correct
9 Correct 11 ms 7344 KB Output is correct
10 Correct 51 ms 8564 KB Output is correct
11 Correct 2 ms 8564 KB Output is correct
12 Correct 3 ms 8564 KB Output is correct
13 Correct 24 ms 8564 KB Output is correct
14 Correct 2 ms 8564 KB Output is correct
15 Correct 69 ms 9428 KB Output is correct

Subtask #4
5.0 / 5.0

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

Subtask #5
10.0 / 10.0

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

Subtask #6
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 9428 KB Output is correct
2 Correct 2 ms 9428 KB Output is correct
3 Correct 2 ms 9428 KB Output is correct
4 Correct 2 ms 9428 KB Output is correct
5 Correct 2 ms 9428 KB Output is correct
6 Correct 2 ms 9428 KB Output is correct
7 Correct 2 ms 9428 KB Output is correct
8 Correct 4 ms 9428 KB Output is correct
9 Correct 3 ms 9428 KB Output is correct
10 Correct 3 ms 9428 KB Output is correct
11 Correct 14 ms 9428 KB Output is correct
12 Correct 28 ms 9428 KB Output is correct
13 Correct 20 ms 9428 KB Output is correct
14 Correct 15 ms 9428 KB Output is correct
15 Correct 22 ms 9428 KB Output is correct

Subtask #7
5.0 / 5.0

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

Subtask #8
15.0 / 15.0

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

Subtask #9
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 9428 KB Output is correct
2 Correct 2 ms 9428 KB Output is correct
3 Correct 2 ms 9428 KB Output is correct
4 Correct 2 ms 9428 KB Output is correct
5 Correct 3 ms 9428 KB Output is correct
6 Correct 2 ms 9428 KB Output is correct
7 Correct 2 ms 9428 KB Output is correct
8 Correct 3 ms 9428 KB Output is correct
9 Correct 72 ms 12096 KB Output is correct
10 Correct 71 ms 12096 KB Output is correct
11 Correct 18 ms 12096 KB Output is correct
12 Correct 22 ms 12096 KB Output is correct
13 Correct 6 ms 12096 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 12096 KB Output is correct
2 Correct 2 ms 12096 KB Output is correct
3 Correct 3 ms 12096 KB Output is correct
4 Correct 2 ms 12096 KB Output is correct
5 Correct 2 ms 12096 KB Output is correct
6 Correct 2 ms 12096 KB Output is correct
7 Correct 3 ms 12096 KB Output is correct
8 Correct 2 ms 12096 KB Output is correct
9 Correct 54 ms 13540 KB Output is correct
10 Correct 46 ms 13540 KB Output is correct
11 Correct 17 ms 13540 KB Output is correct
12 Correct 27 ms 13540 KB Output is correct
13 Correct 9 ms 13540 KB Output is correct
14 Correct 85 ms 15808 KB Output is correct
15 Correct 104 ms 17284 KB Output is correct
16 Correct 17 ms 17284 KB Output is correct
17 Correct 61 ms 17284 KB Output is correct
18 Correct 32 ms 17284 KB Output is correct