oj.uz

Submission #58383

# Submission time Handle Problem Language Result Execution time Memory
58383 2018-07-17T16:09:12 Z aome Gondola (IOI14_gondola) C++17
60 / 100
 91 ms 4884 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] : 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 128 KB Output is correct
2 Correct 3 ms 248 KB Output is correct
3 Correct 2 ms 324 KB Output is correct
4 Correct 2 ms 528 KB Output is correct
5 Correct 2 ms 528 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 528 KB Output is correct
2 Correct 3 ms 528 KB Output is correct
3 Correct 3 ms 528 KB Output is correct
4 Correct 3 ms 528 KB Output is correct
5 Correct 2 ms 528 KB Output is correct
6 Correct 20 ms 2496 KB Output is correct
7 Correct 15 ms 2496 KB Output is correct
8 Correct 37 ms 4072 KB Output is correct
9 Correct 17 ms 4072 KB Output is correct
10 Correct 52 ms 4776 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4776 KB Output is correct
2 Correct 3 ms 4776 KB Output is correct
3 Correct 3 ms 4776 KB Output is correct
4 Correct 4 ms 4776 KB Output is correct
5 Correct 3 ms 4776 KB Output is correct
6 Correct 21 ms 4776 KB Output is correct
7 Correct 17 ms 4776 KB Output is correct
8 Correct 45 ms 4776 KB Output is correct
9 Correct 14 ms 4776 KB Output is correct
10 Correct 58 ms 4776 KB Output is correct
11 Correct 2 ms 4776 KB Output is correct
12 Correct 3 ms 4776 KB Output is correct
13 Correct 33 ms 4776 KB Output is correct
14 Correct 3 ms 4776 KB Output is correct
15 Correct 91 ms 4884 KB Output is correct

Subtask #4
5.0 / 5.0

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

Subtask #5
10.0 / 10.0

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

Subtask #6
20.0 / 20.0

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

Subtask #7
5.0 / 5.0

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

Subtask #8
0 / 15.0

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

Subtask #9
0 / 15.0

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

Subtask #10
0 / 10.0

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