oj.uz

Submission #153501

# Submission time Handle Problem Language Result Execution time Memory
153501 2019-09-14T11:20:27 Z dennisstar Gondola (IOI14_gondola) C++11
75 / 100
 23 ms 3248 KB 
#include "gondola.h"
#include <bits/stdc++.h>
using namespace std;
int valid(int n, int inputSeq[])
{
	int i;
	int chk[250010];
	memset(chk, 0, sizeof(chk));
	for (i=0; i<n; i++) chk[inputSeq[i]]++;
	for (i=0; i<n; i++) if (chk[inputSeq[i]]!=1) return 0;
	for (i=0; i<n; i++) if (inputSeq[i]<=n) break;
	if (i>=n) return 1;
	int ar[100010];
	for (int j=0; j<n; j++) ar[(inputSeq[i]-1+j)%n]=inputSeq[(i+j)%n];
	for (i=0; i<n; i++) if (ar[i]<=n&&i+1!=ar[i]) return 0;
	return 1;
}

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

int replacement(int n, int gondolaSeq[], int replacementSeq[])
{
	int chk[250010]; int i, j;
	int ar[100010];
	memset(chk, 0, sizeof(chk));
	int mx=0;
	for (i=0; i<n; i++) mx=max(mx, gondolaSeq[i]);
	for (i=0; i<n; i++) if (gondolaSeq[i]<=n) break;
	if (i<n) {
		for (j=0; j<n; j++) ar[(gondolaSeq[i]-1+j)%n]=gondolaSeq[(i+j)%n];
 		for (i=0; i<n; i++) gondolaSeq[i]=ar[i];
	}
	for (i=0; i<n; i++) chk[gondolaSeq[i]]=i+1;
	int fr=0;
	for (i=0; i<n; i++) ar[i]=i+1;
	for (i=n+1; i<=mx; i++) {
		if (chk[i]) {
			replacementSeq[i-n-1]=ar[chk[i]-1];
			ar[chk[i]-1]=i;
		}
		else {
			for (; ar[fr]==gondolaSeq[fr]; fr++) {}
			replacementSeq[i-n-1]=ar[fr];
			ar[fr]=i;
		}
	}
	return mx-n;
}

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

int countReplacement(int n, int gondolaSeq[])
{
	int chk[250010]; int i, j;
	

	memset(chk, 0, sizeof(chk));
	for (i=0; i<n; i++) chk[gondolaSeq[i]]++;
	for (i=0; i<n; i++) if (chk[gondolaSeq[i]]!=1) return 0;
	for (i=0; i<n; i++) if (gondolaSeq[i]<=n) break;
	if (i<n) {
		int arr[100010];
		for (j=0; j<n; j++) arr[(gondolaSeq[i]-1+j)%n]=gondolaSeq[(i+j)%n];
		for (i=0; i<n; i++) if (arr[i]<=n&&i+1!=arr[i]) return 0;
	}



	int ar[100010];
	memset(chk, 0, sizeof(chk));
	int mx=0;
	for (i=0; i<n; i++) mx=max(mx, gondolaSeq[i]);
	for (i=0; i<n; i++) if (gondolaSeq[i]<=n) break;
	if (i<n) {
		for (j=0; j<n; j++) ar[(gondolaSeq[i]-1+j)%n]=gondolaSeq[(i+j)%n];
 		for (i=0; i<n; i++) gondolaSeq[i]=ar[i];
	}
	for (i=0; i<n; i++) chk[gondolaSeq[i]]=i+1;
	for (i=0; i<n; i++) ar[i]=i+1;
	int cnt=0;
	for (i=0; i<n; i++) if (gondolaSeq[i]>n) cnt++;
	long long ret=1;
	for (i=n+1; i<=mx; i++) {
		if (!chk[i]) {
			ret*=(long long)cnt; ret%=1000000009ll;
		}
		else cnt--;
	}
	return (int)ret;
}

Subtask #1
5.0 / 5.0

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

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1272 KB Output is correct
2 Correct 3 ms 1400 KB Output is correct
3 Correct 3 ms 1272 KB Output is correct
4 Correct 3 ms 1264 KB Output is correct
5 Correct 3 ms 1272 KB Output is correct
6 Correct 8 ms 1784 KB Output is correct
7 Correct 15 ms 2168 KB Output is correct
8 Correct 12 ms 2296 KB Output is correct
9 Correct 6 ms 1656 KB Output is correct
10 Correct 14 ms 2424 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1296 KB Output is correct
2 Correct 3 ms 1272 KB Output is correct
3 Correct 3 ms 1272 KB Output is correct
4 Correct 3 ms 1244 KB Output is correct
5 Correct 3 ms 1272 KB Output is correct
6 Correct 8 ms 1788 KB Output is correct
7 Correct 15 ms 2120 KB Output is correct
8 Correct 12 ms 2296 KB Output is correct
9 Correct 6 ms 1576 KB Output is correct
10 Correct 16 ms 2424 KB Output is correct
11 Correct 3 ms 1272 KB Output is correct
12 Correct 3 ms 1272 KB Output is correct
13 Correct 10 ms 1788 KB Output is correct
14 Correct 3 ms 1256 KB Output is correct
15 Correct 17 ms 2424 KB Output is correct

Subtask #4
5.0 / 5.0

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

Subtask #5
10.0 / 10.0

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

Subtask #6
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1420 KB Output is correct
2 Correct 3 ms 1272 KB Output is correct
3 Correct 3 ms 1272 KB Output is correct
4 Correct 3 ms 1272 KB Output is correct
5 Correct 3 ms 1260 KB Output is correct
6 Correct 3 ms 1272 KB Output is correct
7 Correct 3 ms 1372 KB Output is correct
8 Correct 3 ms 1400 KB Output is correct
9 Correct 3 ms 1272 KB Output is correct
10 Correct 3 ms 1400 KB Output is correct
11 Correct 14 ms 2296 KB Output is correct
12 Correct 15 ms 2524 KB Output is correct
13 Correct 16 ms 2412 KB Output is correct
14 Correct 14 ms 2296 KB Output is correct
15 Correct 23 ms 3248 KB Output is correct

Subtask #7
5.0 / 5.0

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

Subtask #8
15.0 / 15.0

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

Subtask #9
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1272 KB Output is correct
2 Correct 3 ms 1272 KB Output is correct
3 Correct 3 ms 1276 KB Output is correct
4 Correct 3 ms 1272 KB Output is correct
5 Correct 3 ms 1272 KB Output is correct
6 Correct 3 ms 1244 KB Output is correct
7 Correct 3 ms 1272 KB Output is correct
8 Correct 3 ms 1272 KB Output is correct
9 Correct 17 ms 2296 KB Output is correct
10 Correct 12 ms 2168 KB Output is correct
11 Correct 9 ms 1656 KB Output is correct
12 Correct 9 ms 1628 KB Output is correct
13 Incorrect 6 ms 1400 KB Output isn't correct

Subtask #10
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1272 KB Output is correct
2 Correct 3 ms 1272 KB Output is correct
3 Correct 3 ms 1272 KB Output is correct
4 Correct 3 ms 1272 KB Output is correct
5 Correct 3 ms 1276 KB Output is correct
6 Correct 3 ms 1272 KB Output is correct
7 Correct 3 ms 1272 KB Output is correct
8 Correct 3 ms 1276 KB Output is correct
9 Correct 15 ms 2424 KB Output is correct
10 Correct 15 ms 2208 KB Output is correct
11 Correct 9 ms 1660 KB Output is correct
12 Correct 9 ms 1656 KB Output is correct
13 Incorrect 7 ms 1404 KB Output isn't correct
14 Halted 0 ms 0 KB -