oj.uz

Submission #60527

# Submission time Handle Problem Language Result Execution time Memory
60527 2018-07-24T10:01:43 Z hamzqq9 Gondola (IOI14_gondola) C++14
75 / 100
 33 ms 8040 KB 
#include "gondola.h"
#define st first
#define nd second
#define ii pair<int,int> 
#define pb push_back
#define sz(x) (x.size())
#include<bits/stdc++.h>
using namespace std;

int find_fixed(int n,int inputSeq[]) {

	int fixed=0;

	for(int i=0;i<n;i++) {

		if(inputSeq[i]<=n) {

			fixed=i;

			break ;

		}

	}

	return fixed;

}

int valid(int n, int inputSeq[]) {

	int fr[250001]={0};

	int fixed=find_fixed(n,inputSeq);

	int tot=2,big=0;

	int cur=inputSeq[fixed];

	for(int i=fixed;(tot-=(i==fixed));i=(i+1)%n,cur++) {

		if(cur>n) cur-=n;

		if(inputSeq[i]>n) {
		
			fr[inputSeq[i]]++;

			big++;

			continue ;
		
		}

		if(inputSeq[i]!=cur) return 0;

	}

	for(int i=n+1;i<250001;i++) {

		if(fr[i]>1) return 0; 

	}

	return 1;

}

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

int replacement(int n, int gondolaSeq[], int replacementSeq[]) {

	int fixed=find_fixed(n,gondolaSeq);

	int cur=(gondolaSeq[fixed]<=n?gondolaSeq[fixed]:1);
	int tot=2;

	vector<ii> change;

	for(int i=fixed;(tot-=(i==fixed));i=(i+1)%n,cur++) {

		if(cur>n) cur-=n;

		if(gondolaSeq[i]>n) {

			change.pb({gondolaSeq[i],cur});

		}

	}

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

	int sz=0;
	int val=n;

	for(int i=0;i<sz(change);i++) {

		auto x=change[i];

		replacementSeq[sz++]=x.nd;

		val++;

		while(val<x.st) {

			replacementSeq[sz++]=val++;

		}

	}

	return sz;

}
#define MOD 1000000009
//----------------------

int fe(int x,int y) {

	if(y==0) return 1;
	if(y==1) return x;

	int res=fe(x,y/2);

	res=1ll*res*res%MOD;

	if(y&1) return 1ll*res*x%MOD;

	return res;

}

int countReplacement(int n, int inputSeq[]) {

	int isvalid=valid(n,inputSeq);

	int ans=1;

	vector<int> ranges;

	if(!isvalid) return 0;

	for(int i=0;i<n;i++) {

		if(inputSeq[i]<=n) continue ;

		ranges.pb(inputSeq[i]);

	}

	ranges.pb(n);

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

	int cursz=sz(ranges)-1;

	for(int i=1;i<sz(ranges);i++,cursz--) {

		int range=ranges[i]-ranges[i-1]-1;

		ans=1ll*ans*fe(cursz,range)%MOD;

	}

	return ans;

}

Compilation message

gondola.cpp: In function 'int replacement(int, int*, int*)':
gondola.cpp:96:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<sz(change);i++) {
               ^
gondola.cpp: In function 'int countReplacement(int, int*)':
gondola.cpp:157:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=1;i<sz(ranges);i++,cursz--) {
               ^

Subtask #1
5.0 / 5.0

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

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 1528 KB Output is correct
2 Correct 4 ms 1528 KB Output is correct
3 Correct 4 ms 1568 KB Output is correct
4 Correct 4 ms 1568 KB Output is correct
5 Correct 4 ms 1568 KB Output is correct
6 Correct 9 ms 1992 KB Output is correct
7 Correct 16 ms 2584 KB Output is correct
8 Correct 17 ms 2928 KB Output is correct
9 Correct 9 ms 2928 KB Output is correct
10 Correct 18 ms 3612 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 3612 KB Output is correct
2 Correct 4 ms 3612 KB Output is correct
3 Correct 4 ms 3612 KB Output is correct
4 Correct 4 ms 3612 KB Output is correct
5 Correct 3 ms 3612 KB Output is correct
6 Correct 9 ms 3680 KB Output is correct
7 Correct 19 ms 4376 KB Output is correct
8 Correct 15 ms 4744 KB Output is correct
9 Correct 10 ms 4768 KB Output is correct
10 Correct 20 ms 5292 KB Output is correct
11 Correct 3 ms 5292 KB Output is correct
12 Correct 4 ms 5292 KB Output is correct
13 Correct 11 ms 5292 KB Output is correct
14 Correct 5 ms 5292 KB Output is correct
15 Correct 20 ms 5392 KB Output is correct

Subtask #4
5.0 / 5.0

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

Subtask #5
10.0 / 10.0

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

Subtask #6
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 5392 KB Output is correct
2 Correct 3 ms 5392 KB Output is correct
3 Correct 3 ms 5392 KB Output is correct
4 Correct 3 ms 5392 KB Output is correct
5 Correct 3 ms 5392 KB Output is correct
6 Correct 2 ms 5392 KB Output is correct
7 Correct 4 ms 5392 KB Output is correct
8 Correct 3 ms 5392 KB Output is correct
9 Correct 3 ms 5392 KB Output is correct
10 Correct 3 ms 5392 KB Output is correct
11 Correct 19 ms 5392 KB Output is correct
12 Correct 23 ms 5392 KB Output is correct
13 Correct 29 ms 5392 KB Output is correct
14 Correct 19 ms 5392 KB Output is correct
15 Correct 33 ms 5952 KB Output is correct

Subtask #7
5.0 / 5.0

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

Subtask #8
15.0 / 15.0

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

Subtask #9
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 5952 KB Output is correct
2 Correct 5 ms 5952 KB Output is correct
3 Correct 4 ms 5952 KB Output is correct
4 Correct 4 ms 5952 KB Output is correct
5 Correct 3 ms 5952 KB Output is correct
6 Correct 4 ms 5952 KB Output is correct
7 Correct 4 ms 5952 KB Output is correct
8 Correct 4 ms 5952 KB Output is correct
9 Correct 25 ms 6388 KB Output is correct
10 Correct 20 ms 6868 KB Output is correct
11 Correct 11 ms 6868 KB Output is correct
12 Correct 13 ms 6868 KB Output is correct
13 Incorrect 7 ms 6868 KB Output isn't correct

Subtask #10
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 6868 KB Output is correct
2 Correct 4 ms 6868 KB Output is correct
3 Correct 3 ms 6868 KB Output is correct
4 Correct 4 ms 6868 KB Output is correct
5 Correct 4 ms 6868 KB Output is correct
6 Correct 5 ms 6868 KB Output is correct
7 Correct 4 ms 6868 KB Output is correct
8 Correct 4 ms 6868 KB Output is correct
9 Correct 24 ms 7704 KB Output is correct
10 Correct 21 ms 8012 KB Output is correct
11 Correct 15 ms 8012 KB Output is correct
12 Correct 13 ms 8040 KB Output is correct
13 Incorrect 6 ms 8040 KB Output isn't correct
14 Halted 0 ms 0 KB -