oj.uz

Submission #58388

# Submission time Handle Problem Language Result Execution time Memory
58388 2018-07-17T16:20:13 Z aome Gondola (IOI14_gondola) C++17
75 / 100
 88 ms 4988 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;
	}
	if (vec.size() == n) {
		for (int i = 1; i <= n; ++i) res = 1LL * res * i % 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) {
                  ~~^~~~~~~~~~~~
gondola.cpp:78:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  if (vec.size() == n) {
      ~~~~~~~~~~~^~~~

Subtask #1
5.0 / 5.0

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

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 476 KB Output is correct
2 Correct 3 ms 520 KB Output is correct
3 Correct 2 ms 596 KB Output is correct
4 Correct 3 ms 596 KB Output is correct
5 Correct 3 ms 596 KB Output is correct
6 Correct 22 ms 2412 KB Output is correct
7 Correct 19 ms 2412 KB Output is correct
8 Correct 45 ms 4204 KB Output is correct
9 Correct 13 ms 4204 KB Output is correct
10 Correct 49 ms 4716 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4716 KB Output is correct
2 Correct 3 ms 4716 KB Output is correct
3 Correct 3 ms 4716 KB Output is correct
4 Correct 3 ms 4716 KB Output is correct
5 Correct 3 ms 4716 KB Output is correct
6 Correct 25 ms 4716 KB Output is correct
7 Correct 25 ms 4716 KB Output is correct
8 Correct 41 ms 4716 KB Output is correct
9 Correct 16 ms 4716 KB Output is correct
10 Correct 52 ms 4856 KB Output is correct
11 Correct 2 ms 4856 KB Output is correct
12 Correct 3 ms 4856 KB Output is correct
13 Correct 32 ms 4856 KB Output is correct
14 Correct 2 ms 4856 KB Output is correct
15 Correct 75 ms 4988 KB Output is correct

Subtask #4
5.0 / 5.0

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

Subtask #5
10.0 / 10.0

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

Subtask #6
20.0 / 20.0

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

Subtask #7
5.0 / 5.0

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

Subtask #8
15.0 / 15.0

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

Subtask #9
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4988 KB Output is correct
2 Correct 2 ms 4988 KB Output is correct
3 Correct 3 ms 4988 KB Output is correct
4 Correct 3 ms 4988 KB Output is correct
5 Correct 3 ms 4988 KB Output is correct
6 Correct 3 ms 4988 KB Output is correct
7 Correct 3 ms 4988 KB Output is correct
8 Correct 3 ms 4988 KB Output is correct
9 Correct 88 ms 4988 KB Output is correct
10 Correct 74 ms 4988 KB Output is correct
11 Correct 20 ms 4988 KB Output is correct
12 Correct 24 ms 4988 KB Output is correct
13 Incorrect 7 ms 4988 KB Output isn't correct

Subtask #10
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 4988 KB Output is correct
2 Correct 2 ms 4988 KB Output is correct
3 Correct 3 ms 4988 KB Output is correct
4 Correct 3 ms 4988 KB Output is correct
5 Correct 2 ms 4988 KB Output is correct
6 Correct 3 ms 4988 KB Output is correct
7 Correct 2 ms 4988 KB Output is correct
8 Correct 2 ms 4988 KB Output is correct
9 Correct 77 ms 4988 KB Output is correct
10 Correct 54 ms 4988 KB Output is correct
11 Correct 20 ms 4988 KB Output is correct
12 Correct 30 ms 4988 KB Output is correct
13 Incorrect 9 ms 4988 KB Output isn't correct
14 Halted 0 ms 0 KB -