oj.uz

Submission #58381

# Submission time Handle Problem Language Result Execution time Memory
58381 2018-07-17T16:03:59 Z aome Gondola (IOI14_gondola) C++17
25 / 100
 83 ms 9300 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 : 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] : n);
		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 3 ms 376 KB Output is correct
2 Correct 3 ms 376 KB Output is correct
3 Correct 3 ms 420 KB Output is correct
4 Correct 2 ms 480 KB Output is correct
5 Correct 3 ms 484 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 484 KB Output is correct
2 Correct 3 ms 668 KB Output is correct
3 Correct 2 ms 668 KB Output is correct
4 Correct 3 ms 668 KB Output is correct
5 Correct 3 ms 668 KB Output is correct
6 Correct 25 ms 2632 KB Output is correct
7 Correct 20 ms 2632 KB Output is correct
8 Correct 44 ms 5420 KB Output is correct
9 Correct 19 ms 5420 KB Output is correct
10 Correct 58 ms 6548 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 6548 KB Output is correct
2 Correct 3 ms 6548 KB Output is correct
3 Correct 3 ms 6548 KB Output is correct
4 Correct 3 ms 6548 KB Output is correct
5 Correct 4 ms 6548 KB Output is correct
6 Correct 22 ms 6548 KB Output is correct
7 Correct 19 ms 6548 KB Output is correct
8 Correct 44 ms 7160 KB Output is correct
9 Correct 16 ms 7160 KB Output is correct
10 Correct 62 ms 8312 KB Output is correct
11 Correct 3 ms 8312 KB Output is correct
12 Correct 3 ms 8312 KB Output is correct
13 Correct 44 ms 8312 KB Output is correct
14 Correct 3 ms 8312 KB Output is correct
15 Correct 83 ms 9300 KB Output is correct

Subtask #4
5.0 / 5.0

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

Subtask #5
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 9300 KB Output is correct
2 Correct 4 ms 9300 KB Output is correct
3 Correct 3 ms 9300 KB Output is correct
4 Correct 3 ms 9300 KB Output is correct
5 Correct 3 ms 9300 KB Output is correct
6 Correct 3 ms 9300 KB Output is correct
7 Incorrect 3 ms 9300 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #6
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 9300 KB Output is correct
2 Correct 2 ms 9300 KB Output is correct
3 Correct 2 ms 9300 KB Output is correct
4 Correct 3 ms 9300 KB Output is correct
5 Correct 3 ms 9300 KB Output is correct
6 Correct 4 ms 9300 KB Output is correct
7 Incorrect 3 ms 9300 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #7
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 9300 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #8
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 9300 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #9
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 9300 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #10
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 9300 KB Output isn't correct
2 Halted 0 ms 0 KB -