oj.uz

Submission #60817

# Submission time Handle Problem Language Result Execution time Memory
60817 2018-07-24T18:07:29 Z hamzqq9 Gondola (IOI14_gondola) C++14
100 / 100
 127 ms 15688 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[]) {

	map<int,int> fr;

	int fixed=find_fixed(n,inputSeq);

	int tot=2;

	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]]++;

			continue ;
		
		}

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

	}

	for(auto x:fr) {

		if(x.nd>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);

	vector<int> ranges;

	if(!isvalid) return 0;

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

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

		ranges.pb(inputSeq[i]);

	}
	
	int ans=(sz(ranges)==n?n:1);

	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:94: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:147:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  int ans=(sz(ranges)==n?n:1);
                     ^
gondola.cpp:155: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 3 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 416 KB Output is correct
4 Correct 3 ms 420 KB Output is correct
5 Correct 3 ms 480 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 484 KB Output is correct
2 Correct 2 ms 564 KB Output is correct
3 Correct 2 ms 744 KB Output is correct
4 Correct 2 ms 744 KB Output is correct
5 Correct 2 ms 744 KB Output is correct
6 Correct 10 ms 916 KB Output is correct
7 Correct 16 ms 1628 KB Output is correct
8 Correct 13 ms 2004 KB Output is correct
9 Correct 6 ms 2004 KB Output is correct
10 Correct 18 ms 2656 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2656 KB Output is correct
2 Correct 4 ms 2656 KB Output is correct
3 Correct 2 ms 2656 KB Output is correct
4 Correct 4 ms 2656 KB Output is correct
5 Correct 3 ms 2656 KB Output is correct
6 Correct 9 ms 2656 KB Output is correct
7 Correct 18 ms 3352 KB Output is correct
8 Correct 20 ms 3720 KB Output is correct
9 Correct 7 ms 3720 KB Output is correct
10 Correct 20 ms 4380 KB Output is correct
11 Correct 3 ms 4380 KB Output is correct
12 Correct 2 ms 4380 KB Output is correct
13 Correct 10 ms 4612 KB Output is correct
14 Correct 2 ms 4612 KB Output is correct
15 Correct 18 ms 5104 KB Output is correct

Subtask #4
5.0 / 5.0

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

Subtask #5
10.0 / 10.0

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

Subtask #6
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5104 KB Output is correct
2 Correct 2 ms 5104 KB Output is correct
3 Correct 2 ms 5104 KB Output is correct
4 Correct 2 ms 5104 KB Output is correct
5 Correct 2 ms 5104 KB Output is correct
6 Correct 3 ms 5104 KB Output is correct
7 Correct 3 ms 5104 KB Output is correct
8 Correct 3 ms 5104 KB Output is correct
9 Correct 4 ms 5104 KB Output is correct
10 Correct 4 ms 5104 KB Output is correct
11 Correct 17 ms 5584 KB Output is correct
12 Correct 27 ms 6164 KB Output is correct
13 Correct 35 ms 7012 KB Output is correct
14 Correct 14 ms 7012 KB Output is correct
15 Correct 32 ms 8476 KB Output is correct

Subtask #7
5.0 / 5.0

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

Subtask #8
15.0 / 15.0

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

Subtask #9
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 8476 KB Output is correct
2 Correct 2 ms 8476 KB Output is correct
3 Correct 3 ms 8476 KB Output is correct
4 Correct 3 ms 8476 KB Output is correct
5 Correct 3 ms 8476 KB Output is correct
6 Correct 3 ms 8476 KB Output is correct
7 Correct 3 ms 8476 KB Output is correct
8 Correct 3 ms 8476 KB Output is correct
9 Correct 76 ms 10204 KB Output is correct
10 Correct 52 ms 10204 KB Output is correct
11 Correct 18 ms 10204 KB Output is correct
12 Correct 22 ms 10204 KB Output is correct
13 Correct 7 ms 10204 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 10204 KB Output is correct
2 Correct 2 ms 10204 KB Output is correct
3 Correct 3 ms 10204 KB Output is correct
4 Correct 2 ms 10204 KB Output is correct
5 Correct 2 ms 10204 KB Output is correct
6 Correct 4 ms 10204 KB Output is correct
7 Correct 3 ms 10204 KB Output is correct
8 Correct 3 ms 10204 KB Output is correct
9 Correct 71 ms 11324 KB Output is correct
10 Correct 48 ms 11324 KB Output is correct
11 Correct 23 ms 11324 KB Output is correct
12 Correct 24 ms 11324 KB Output is correct
13 Correct 8 ms 11324 KB Output is correct
14 Correct 110 ms 14356 KB Output is correct
15 Correct 127 ms 15688 KB Output is correct
16 Correct 19 ms 15688 KB Output is correct
17 Correct 82 ms 15688 KB Output is correct
18 Correct 38 ms 15688 KB Output is correct