# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
261322 |
2020-08-11T16:15:24 Z |
A02 |
Gondola (IOI14_gondola) |
C++14 |
|
35 ms |
4600 KB |
#include "gondola.h"
#include <algorithm>
#include <set>
#include <iostream>
#include <vector>
#include <utility>
using namespace std;
int valid(int n, int inputSeq[])
{
vector<int> occurences (250001, 0);
vector<int> index (n, -1);
for (int i = 0; i < n; i++){
occurences[inputSeq[i]]++;
if (inputSeq[i] <= n){
//cout << i << ' ' << reduced_sequence[i] << endl;
index[inputSeq[i] - 1] = i;
}
}
for (int i = 0; i < occurences.size(); i++){
if (occurences[i] > 1){
return 0;
}
}
int lowest_g;
for (int i = 0; i < n; i++){
if (index[i] != -1){
lowest_g = i;
break;
}
}
for (int i = lowest_g; i < n; i++){
if (index[i] != -1){
//cout << i << ' ' << index[i] << endl;
if ((index[lowest_g] + i - lowest_g) % n != index[i]){
return 0;
}
}
}
return 1;
}
//----------------------
int replacement(int n, int gondolaSeq[], int replacementSeq[])
{
int first_original = 0;
int first_value = 1;
for (int i = 0; i < n; i++){
if (gondolaSeq[i] <= n){
first_original = i;
first_value = gondolaSeq[i];
}
}
vector<pair<int, int> > to_replace;
for (int i = 0; i < n; i++){
int current_pos = (i + first_original) % n;
int current_original_value = (i + first_value);
if (current_original_value > n){
current_original_value -= n;
}
int target_value = gondolaSeq[current_pos];
//cout << first_value << ' ' << i << ' ' << gondolaSeq[i] << endl;
if (target_value != current_original_value){
to_replace.push_back(make_pair(target_value, current_original_value));
}
}
sort(to_replace.begin(), to_replace.end());
int current_unused = n + 1;
int current_replacement = 0;
//cout << to_replace.size() << endl;
for (int i = 0; i < to_replace.size(); i++){
int c_value = to_replace[i].second;
while (c_value != to_replace[i].first){
replacementSeq[current_replacement] = c_value;
c_value = current_unused;
current_replacement++;
current_unused++;
}
}
return current_replacement;
}
//----------------------
long long fast_pow(long long a, long long k, long long p){
if (k == 0){
return 1;
}
if (a % p == 0){
return 0;
}
if (k % 2 == 1){
long long b = fast_pow(a, k / 2, p);
return ((((b * b) % p) * a) % p);
}
long long b = fast_pow(a, k / 2, p);
return ((b * b) % p);
}
int countReplacement(int n, int inputSeq[])
{
long long p = 1000000009;
if (valid(n, inputSeq) == 0){
return 0;
}
vector<long long> to_replace;
to_replace.push_back(n);
for (long long i = 0; i < n; i++){
if(inputSeq[i] > n){
to_replace.push_back(inputSeq[i]);
}
}
sort(to_replace.begin(), to_replace.end());
long long total = 1;
long long current_options = to_replace.size() - 1;
for (int i = 0; i < to_replace.size() - 1; i++){
//cout << current_options << ' ' << to_replace[i + 1].first << ' ' << to_replace[i].first << endl;
total *= fast_pow(current_options, (to_replace[i + 1] - to_replace[i] - 1), p);
total %= p;
current_options--;
}
if (to_replace.size() == n + 1){
total *= n;
total %= p;
}
return ((int) total);
}
Compilation message
gondola.cpp: In function 'int valid(int, int*)':
gondola.cpp:25:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0; i < occurences.size(); i++){
~~^~~~~~~~~~~~~~~~~~~
gondola.cpp: In function 'int replacement(int, int*, int*)':
gondola.cpp:86:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0; i < to_replace.size(); i++){
~~^~~~~~~~~~~~~~~~~~~
gondola.cpp: In function 'int countReplacement(int, int*)':
gondola.cpp:146:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0; i < to_replace.size() - 1; i++){
~~^~~~~~~~~~~~~~~~~~~~~~~
gondola.cpp:154:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
if (to_replace.size() == n + 1){
~~~~~~~~~~~~~~~~~~^~~~~~~~
gondola.cpp: In function 'int valid(int, int*)':
gondola.cpp:31:9: warning: 'lowest_g' may be used uninitialized in this function [-Wmaybe-uninitialized]
int lowest_g;
^~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
1256 KB |
Output is correct |
2 |
Correct |
1 ms |
1280 KB |
Output is correct |
3 |
Correct |
2 ms |
1276 KB |
Output is correct |
4 |
Correct |
1 ms |
1280 KB |
Output is correct |
5 |
Correct |
1 ms |
1280 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
1280 KB |
Output is correct |
2 |
Correct |
1 ms |
1280 KB |
Output is correct |
3 |
Correct |
1 ms |
1280 KB |
Output is correct |
4 |
Correct |
1 ms |
1280 KB |
Output is correct |
5 |
Correct |
2 ms |
1280 KB |
Output is correct |
6 |
Correct |
10 ms |
1792 KB |
Output is correct |
7 |
Correct |
16 ms |
2432 KB |
Output is correct |
8 |
Correct |
13 ms |
2304 KB |
Output is correct |
9 |
Correct |
5 ms |
1664 KB |
Output is correct |
10 |
Correct |
15 ms |
2432 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
1280 KB |
Output is correct |
2 |
Correct |
1 ms |
1280 KB |
Output is correct |
3 |
Correct |
2 ms |
1280 KB |
Output is correct |
4 |
Correct |
1 ms |
1280 KB |
Output is correct |
5 |
Correct |
2 ms |
1280 KB |
Output is correct |
6 |
Correct |
8 ms |
1792 KB |
Output is correct |
7 |
Correct |
16 ms |
2432 KB |
Output is correct |
8 |
Correct |
13 ms |
2304 KB |
Output is correct |
9 |
Correct |
5 ms |
1664 KB |
Output is correct |
10 |
Correct |
15 ms |
2432 KB |
Output is correct |
11 |
Correct |
1 ms |
1280 KB |
Output is correct |
12 |
Correct |
2 ms |
1280 KB |
Output is correct |
13 |
Correct |
8 ms |
1792 KB |
Output is correct |
14 |
Correct |
1 ms |
1280 KB |
Output is correct |
15 |
Correct |
16 ms |
2432 KB |
Output is correct |
# |
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 |
1 ms |
384 KB |
Output is correct |
4 |
Correct |
1 ms |
384 KB |
Output is correct |
5 |
Correct |
1 ms |
384 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
384 KB |
Output is correct |
2 |
Correct |
1 ms |
384 KB |
Output is correct |
3 |
Correct |
1 ms |
384 KB |
Output is correct |
4 |
Correct |
1 ms |
384 KB |
Output is correct |
5 |
Correct |
1 ms |
384 KB |
Output is correct |
6 |
Correct |
1 ms |
256 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 |
# |
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 |
1 ms |
384 KB |
Output is correct |
4 |
Correct |
1 ms |
384 KB |
Output is correct |
5 |
Correct |
1 ms |
384 KB |
Output is correct |
6 |
Correct |
1 ms |
256 KB |
Output is correct |
7 |
Correct |
1 ms |
512 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 |
512 KB |
Output is correct |
11 |
Correct |
13 ms |
1024 KB |
Output is correct |
12 |
Correct |
15 ms |
1152 KB |
Output is correct |
13 |
Correct |
18 ms |
1552 KB |
Output is correct |
14 |
Correct |
16 ms |
1024 KB |
Output is correct |
15 |
Correct |
35 ms |
2404 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
1280 KB |
Output is correct |
2 |
Correct |
2 ms |
1280 KB |
Output is correct |
3 |
Correct |
2 ms |
1280 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
1280 KB |
Output is correct |
2 |
Correct |
2 ms |
1280 KB |
Output is correct |
3 |
Correct |
2 ms |
1280 KB |
Output is correct |
4 |
Correct |
2 ms |
1280 KB |
Output is correct |
5 |
Correct |
1 ms |
1280 KB |
Output is correct |
6 |
Correct |
2 ms |
1280 KB |
Output is correct |
7 |
Correct |
2 ms |
1280 KB |
Output is correct |
8 |
Correct |
1 ms |
1280 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
1280 KB |
Output is correct |
2 |
Correct |
2 ms |
1280 KB |
Output is correct |
3 |
Correct |
1 ms |
1280 KB |
Output is correct |
4 |
Correct |
1 ms |
1280 KB |
Output is correct |
5 |
Correct |
2 ms |
1312 KB |
Output is correct |
6 |
Correct |
2 ms |
1280 KB |
Output is correct |
7 |
Correct |
2 ms |
1280 KB |
Output is correct |
8 |
Correct |
1 ms |
1280 KB |
Output is correct |
9 |
Correct |
25 ms |
2304 KB |
Output is correct |
10 |
Correct |
18 ms |
2176 KB |
Output is correct |
11 |
Correct |
8 ms |
1664 KB |
Output is correct |
12 |
Correct |
9 ms |
1664 KB |
Output is correct |
13 |
Correct |
3 ms |
1408 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
1280 KB |
Output is correct |
2 |
Correct |
2 ms |
1280 KB |
Output is correct |
3 |
Correct |
2 ms |
1280 KB |
Output is correct |
4 |
Correct |
2 ms |
1280 KB |
Output is correct |
5 |
Correct |
2 ms |
1280 KB |
Output is correct |
6 |
Correct |
2 ms |
1280 KB |
Output is correct |
7 |
Correct |
2 ms |
1280 KB |
Output is correct |
8 |
Correct |
2 ms |
1280 KB |
Output is correct |
9 |
Correct |
28 ms |
2304 KB |
Output is correct |
10 |
Correct |
17 ms |
2176 KB |
Output is correct |
11 |
Correct |
8 ms |
1664 KB |
Output is correct |
12 |
Correct |
9 ms |
1664 KB |
Output is correct |
13 |
Correct |
4 ms |
1408 KB |
Output is correct |
14 |
Runtime error |
21 ms |
4600 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
15 |
Halted |
0 ms |
0 KB |
- |