oj.uz

Submission #60547

# Submission time Handle Problem Language Result Execution time Memory
60547 2018-07-24T10:20:23 Z hamzqq9 Gondola (IOI14_gondola) C++14
75 / 100
 88 ms 3644 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);

	int ans=1;

	vector<int> ranges;

	if(!isvalid && n<=50) 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: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: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 248 KB Output is correct
2 Correct 3 ms 356 KB Output is correct
3 Correct 3 ms 356 KB Output is correct
4 Correct 1 ms 560 KB Output is correct
5 Correct 2 ms 560 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 560 KB Output is correct
2 Correct 2 ms 560 KB Output is correct
3 Correct 2 ms 560 KB Output is correct
4 Correct 3 ms 572 KB Output is correct
5 Correct 3 ms 616 KB Output is correct
6 Correct 9 ms 744 KB Output is correct
7 Correct 15 ms 872 KB Output is correct
8 Correct 12 ms 872 KB Output is correct
9 Correct 6 ms 872 KB Output is correct
10 Correct 18 ms 872 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 872 KB Output is correct
2 Correct 2 ms 872 KB Output is correct
3 Correct 2 ms 872 KB Output is correct
4 Correct 2 ms 872 KB Output is correct
5 Correct 2 ms 872 KB Output is correct
6 Correct 11 ms 872 KB Output is correct
7 Correct 18 ms 876 KB Output is correct
8 Correct 20 ms 880 KB Output is correct
9 Correct 9 ms 880 KB Output is correct
10 Correct 15 ms 880 KB Output is correct
11 Correct 2 ms 880 KB Output is correct
12 Correct 3 ms 880 KB Output is correct
13 Correct 11 ms 880 KB Output is correct
14 Correct 3 ms 880 KB Output is correct
15 Correct 21 ms 880 KB Output is correct

Subtask #4
5.0 / 5.0

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

Subtask #5
10.0 / 10.0

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

Subtask #6
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 880 KB Output is correct
2 Correct 3 ms 880 KB Output is correct
3 Correct 3 ms 880 KB Output is correct
4 Correct 2 ms 880 KB Output is correct
5 Correct 2 ms 880 KB Output is correct
6 Correct 3 ms 880 KB Output is correct
7 Correct 3 ms 880 KB Output is correct
8 Correct 4 ms 880 KB Output is correct
9 Correct 4 ms 880 KB Output is correct
10 Correct 4 ms 880 KB Output is correct
11 Correct 21 ms 956 KB Output is correct
12 Correct 16 ms 1028 KB Output is correct
13 Correct 19 ms 1600 KB Output is correct
14 Correct 20 ms 1600 KB Output is correct
15 Correct 31 ms 2556 KB Output is correct

Subtask #7
5.0 / 5.0

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

Subtask #8
15.0 / 15.0

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

Subtask #9
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2556 KB Output is correct
2 Correct 3 ms 2556 KB Output is correct
3 Correct 5 ms 2556 KB Output is correct
4 Correct 2 ms 2556 KB Output is correct
5 Correct 3 ms 2556 KB Output is correct
6 Correct 3 ms 2556 KB Output is correct
7 Correct 3 ms 2556 KB Output is correct
8 Correct 4 ms 2556 KB Output is correct
9 Correct 80 ms 3644 KB Output is correct
10 Correct 56 ms 3644 KB Output is correct
11 Correct 19 ms 3644 KB Output is correct
12 Correct 31 ms 3644 KB Output is correct
13 Incorrect 6 ms 3644 KB Output isn't correct

Subtask #10
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 3644 KB Output is correct
2 Correct 3 ms 3644 KB Output is correct
3 Correct 2 ms 3644 KB Output is correct
4 Correct 3 ms 3644 KB Output is correct
5 Correct 2 ms 3644 KB Output is correct
6 Correct 2 ms 3644 KB Output is correct
7 Correct 3 ms 3644 KB Output is correct
8 Correct 2 ms 3644 KB Output is correct
9 Correct 88 ms 3644 KB Output is correct
10 Correct 40 ms 3644 KB Output is correct
11 Correct 21 ms 3644 KB Output is correct
12 Correct 32 ms 3644 KB Output is correct
13 Incorrect 8 ms 3644 KB Output isn't correct
14 Halted 0 ms 0 KB -