oj.uz

Submission #58385

# Submission time Handle Problem Language Result Execution time Memory
58385 2018-07-17T16:09:57 Z aome Gondola (IOI14_gondola) C++17
75 / 100
 91 ms 6552 KB 
#include "gondola.h"

#include <bits/stdc++.h>

using namespace std;

int valid(int n, int inputSeq[]) {
	map<int, int> mp;
  	for (int i = 0; i < n; ++i) {
  		if (mp[inputSeq[i]]) return 0;
  		mp[inputSeq[i]] = 1;
  	}
  	int pos = -1;
  	for (int i = 0; i < n; ++i) {
  		if (inputSeq[i] <= n) pos = i;
  	}
  	if (pos == -1) return 1;
  	for (int i = 0; i < n; ++i) {
  		if (inputSeq[i] <= n && inputSeq[i] != (inputSeq[pos] - 1 + i - pos + n) % n + 1) return 0;
  	}
  	return 1;
}

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

int arr[100005];

int replacement(int n, int gondolaSeq[], int replacementSeq[]) {
	int pos = -1;
	int start = -1;
	vector< pair<int, int> > vec;
	for (int i = 0; i < n; ++i) {
		if (gondolaSeq[i] <= n) pos = i, start = gondolaSeq[i];
	}
	if (pos == -1) pos = 0, start = 1;
	for (int i = 0; i < n; ++i) {
		arr[(i + pos) % n] = (start - 1 + i) % n + 1;
	}
	for (int i = 0; i < n; ++i) {
		if (gondolaSeq[i] > n) vec.push_back({gondolaSeq[i], arr[i]});
	}
	sort(vec.begin(), vec.end());
	int sz = 0;
	for (int i = 0; i < vec.size(); ++i) {
		int tmp = (i > 0 ? vec[i - 1].first + 1 : n + 1);
		replacementSeq[sz++] = vec[i].second;
		for (int j = tmp; j < vec[i].first; ++j) {
			replacementSeq[sz++] = j;
		}
	}
	return sz;
}

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

const int mod = 1e9 + 9;

int binPow(int x, int y) {
	if (!y) return 1;
	int ret = binPow(x, y >> 1);
	ret = 1LL * ret * ret % mod;
	if (y & 1) ret = 1LL * ret * x % mod;
	return ret;
}

int countReplacement(int n, int inputSeq[]) {
	if (!valid(n, inputSeq)) return 0;
	int res = 1;
	vector<int> vec;
	for (int i = 0; i < n; ++i) {
		if (inputSeq[i] > n) vec.push_back(inputSeq[i]);
	}
	sort(vec.begin(), vec.end());
	for (int i = 0; i < vec.size(); ++i) {
		int tmp = (i > 0 ? vec[i - 1] + 1 : n + 1);
		res = 1LL * res * binPow(vec.size() - i, vec[i] - tmp) % mod;
	}
	return res;
}

Compilation message

gondola.cpp: In function 'int replacement(int, int*, int*)':
gondola.cpp:44:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < vec.size(); ++i) {
                  ~~^~~~~~~~~~~~
gondola.cpp: In function 'int countReplacement(int, int*)':
gondola.cpp:74:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < vec.size(); ++i) {
                  ~~^~~~~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 248 KB Output is correct
2 Correct 3 ms 356 KB Output is correct
3 Correct 2 ms 356 KB Output is correct
4 Correct 2 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 3 ms 560 KB Output is correct
3 Correct 2 ms 560 KB Output is correct
4 Correct 3 ms 560 KB Output is correct
5 Correct 2 ms 560 KB Output is correct
6 Correct 22 ms 2408 KB Output is correct
7 Correct 20 ms 2408 KB Output is correct
8 Correct 44 ms 4224 KB Output is correct
9 Correct 14 ms 4224 KB Output is correct
10 Correct 63 ms 4724 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4724 KB Output is correct
2 Correct 2 ms 4724 KB Output is correct
3 Correct 3 ms 4724 KB Output is correct
4 Correct 2 ms 4724 KB Output is correct
5 Correct 2 ms 4724 KB Output is correct
6 Correct 28 ms 4724 KB Output is correct
7 Correct 26 ms 4724 KB Output is correct
8 Correct 49 ms 4724 KB Output is correct
9 Correct 17 ms 4724 KB Output is correct
10 Correct 50 ms 4808 KB Output is correct
11 Correct 3 ms 4808 KB Output is correct
12 Correct 2 ms 4808 KB Output is correct
13 Correct 37 ms 4808 KB Output is correct
14 Correct 2 ms 4808 KB Output is correct
15 Correct 78 ms 5000 KB Output is correct

Subtask #4
5.0 / 5.0

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

Subtask #5
10.0 / 10.0

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

Subtask #6
20.0 / 20.0

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

Subtask #7
5.0 / 5.0

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

Subtask #8
15.0 / 15.0

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

Subtask #9
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5000 KB Output is correct
2 Correct 3 ms 5000 KB Output is correct
3 Correct 2 ms 5000 KB Output is correct
4 Correct 3 ms 5000 KB Output is correct
5 Correct 2 ms 5000 KB Output is correct
6 Correct 3 ms 5000 KB Output is correct
7 Correct 4 ms 5000 KB Output is correct
8 Correct 2 ms 5000 KB Output is correct
9 Correct 90 ms 5100 KB Output is correct
10 Correct 55 ms 5100 KB Output is correct
11 Correct 22 ms 5100 KB Output is correct
12 Correct 31 ms 5100 KB Output is correct
13 Incorrect 7 ms 5100 KB Output isn't correct

Subtask #10
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 5100 KB Output is correct
2 Correct 2 ms 5100 KB Output is correct
3 Correct 3 ms 5100 KB Output is correct
4 Correct 3 ms 5100 KB Output is correct
5 Correct 3 ms 5100 KB Output is correct
6 Correct 3 ms 5100 KB Output is correct
7 Correct 3 ms 5100 KB Output is correct
8 Correct 4 ms 5100 KB Output is correct
9 Correct 91 ms 6552 KB Output is correct
10 Correct 82 ms 6552 KB Output is correct
11 Correct 19 ms 6552 KB Output is correct
12 Correct 25 ms 6552 KB Output is correct
13 Incorrect 6 ms 6552 KB Output isn't correct
14 Halted 0 ms 0 KB -