oj.uz

Submission #285674

# Submission time Handle Problem Language Result Execution time Memory
285674 2020-08-29T12:05:05 Z Saboon Gondola (IOI14_gondola) C++14
100 / 100
 37 ms 3196 KB 
#include "gondola.h"
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5 + 10;
const int mod = 1e9+9;

int valid(int n, int inputSeq[]){
	vector<int> A;
	for (int i = 0; i < n; i++)
		A.push_back(inputSeq[i]);
	sort(A.begin(),A.end());
	for (int i = 1; i < n; i++)
		if (A[i] == A[i-1])
			return 0;
	int idx = min_element(inputSeq, inputSeq+n) - inputSeq;
	if (inputSeq[idx] > n)
		return true;
	int cnt = 0;
	for (int i = idx; i < n; i++){
		if (inputSeq[i] <= n and inputSeq[idx]+cnt != inputSeq[i])
			return false;
		cnt ++;
	}
	for (int i = 0; i < idx; i++){
		if (inputSeq[i] <= n and inputSeq[idx]+cnt != inputSeq[i])
			return false;
		cnt ++;
	}
	return true;
}

int p[maxn];

int replacement(int n, int gondolaSeq[], int replacementSeq[]){
	for (int i = 0; i < n; i++)
		p[i] = i+1;
	for (int i = 0; i < n; i++){
		if (gondolaSeq[i] > n)
			continue;
		int cnt = 0;
		for (int j = i; j < n; j++)
			p[j] = (gondolaSeq[i]+cnt-1)%n+1, cnt++;
		for (int j = 0; j < i; j++)
			p[j] = (gondolaSeq[i]+cnt-1)%n+1, cnt++;
		break;
	}
	vector<pair<int,int>> A;
	for (int i = 0; i < n; i++)
		A.push_back({gondolaSeq[i],i});
	sort(A.begin(),A.end());
	int l = 0, now = n+1;
	for (auto it : A){
		int i = it.second;
		if (gondolaSeq[i] <= n)
			continue;
		while (now <= gondolaSeq[i])
			replacementSeq[l++] = p[i], p[i] = now++;
	}
	return l;
}

int power(int a, int b){
	if (b == 0)
		return 1;
	int ret = power(a,b/2);
	ret = 1LL*ret*ret%mod;
	if (b&1)
		ret = 1LL*ret*a%mod;
	return ret;
}

int countReplacement(int n, int inputSeq[]){
	if (!valid(n, inputSeq))
		return 0;
	int Z = 1;
	if (*min_element(inputSeq,inputSeq+n) > n)
		Z = n;
	vector<pair<int,int>> A;
	for (int i = 0; i < n; i++)
		if (inputSeq[i] > n)
			A.push_back({inputSeq[i],i});
	sort(A.begin(),A.end());
	int now = n, m = A.size();
	int mx = *max_element(inputSeq,inputSeq+n);
	for (int i = 0; i < A.size(); i++){
		int diff = A[i].first-now;
		Z = 1LL*Z*power(m,diff-1)%mod;
		m --, now = A[i].first;
	}
	return Z;
}

Compilation message

gondola.cpp: In function 'int countReplacement(int, int*)':
gondola.cpp:85:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   85 |  for (int i = 0; i < A.size(); i++){
      |                  ~~^~~~~~~~~~
gondola.cpp:84:6: warning: unused variable 'mx' [-Wunused-variable]
   84 |  int mx = *max_element(inputSeq,inputSeq+n);
      |      ^~

Subtask #1
5.0 / 5.0

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

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 416 KB Output is correct
2 Correct 0 ms 256 KB Output is correct
3 Correct 0 ms 256 KB Output is correct
4 Correct 1 ms 256 KB Output is correct
5 Correct 0 ms 256 KB Output is correct
6 Correct 8 ms 896 KB Output is correct
7 Correct 19 ms 1276 KB Output is correct
8 Correct 13 ms 1276 KB Output is correct
9 Correct 5 ms 640 KB Output is correct
10 Correct 18 ms 1276 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 1 ms 256 KB Output is correct
3 Correct 0 ms 256 KB Output is correct
4 Correct 0 ms 384 KB Output is correct
5 Correct 0 ms 256 KB Output is correct
6 Correct 8 ms 896 KB Output is correct
7 Correct 20 ms 1276 KB Output is correct
8 Correct 13 ms 1276 KB Output is correct
9 Correct 5 ms 640 KB Output is correct
10 Correct 18 ms 1276 KB Output is correct
11 Correct 0 ms 256 KB Output is correct
12 Correct 0 ms 256 KB Output is correct
13 Correct 9 ms 896 KB Output is correct
14 Correct 0 ms 256 KB Output is correct
15 Correct 21 ms 1276 KB Output is correct

Subtask #4
5.0 / 5.0

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

Subtask #5
10.0 / 10.0

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

Subtask #6
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 0 ms 256 KB Output is correct
5 Correct 0 ms 256 KB Output is correct
6 Correct 1 ms 384 KB Output is correct
7 Correct 1 ms 384 KB Output is correct
8 Correct 1 ms 384 KB Output is correct
9 Correct 1 ms 384 KB Output is correct
10 Correct 1 ms 384 KB Output is correct
11 Correct 18 ms 2040 KB Output is correct
12 Correct 18 ms 2168 KB Output is correct
13 Correct 18 ms 1384 KB Output is correct
14 Correct 14 ms 2168 KB Output is correct
15 Correct 24 ms 2296 KB Output is correct

Subtask #7
5.0 / 5.0

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

Subtask #8
15.0 / 15.0

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

Subtask #9
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 256 KB Output is correct
2 Correct 0 ms 256 KB Output is correct
3 Correct 0 ms 256 KB Output is correct
4 Correct 1 ms 256 KB Output is correct
5 Correct 0 ms 256 KB Output is correct
6 Correct 1 ms 256 KB Output is correct
7 Correct 0 ms 256 KB Output is correct
8 Correct 0 ms 256 KB Output is correct
9 Correct 25 ms 1624 KB Output is correct
10 Correct 19 ms 1292 KB Output is correct
11 Correct 8 ms 808 KB Output is correct
12 Correct 10 ms 788 KB Output is correct
13 Correct 3 ms 512 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 256 KB Output is correct
2 Correct 0 ms 256 KB Output is correct
3 Correct 1 ms 256 KB Output is correct
4 Correct 0 ms 256 KB Output is correct
5 Correct 1 ms 256 KB Output is correct
6 Correct 1 ms 384 KB Output is correct
7 Correct 0 ms 256 KB Output is correct
8 Correct 0 ms 256 KB Output is correct
9 Correct 25 ms 1624 KB Output is correct
10 Correct 19 ms 1292 KB Output is correct
11 Correct 11 ms 808 KB Output is correct
12 Correct 10 ms 788 KB Output is correct
13 Correct 3 ms 640 KB Output is correct
14 Correct 33 ms 2216 KB Output is correct
15 Correct 37 ms 3196 KB Output is correct
16 Correct 7 ms 952 KB Output is correct
17 Correct 24 ms 1920 KB Output is correct
18 Correct 14 ms 1648 KB Output is correct