Submission #261297

#TimeUsernameProblemLanguageResultExecution timeMemory
261297A02Gondola (IOI14_gondola)C++14
75 / 100
25 ms2560 KiB
#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 (a % p == 0){ return 0; } if (k == 0){ return 1; } 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 = (total * fast_pow(current_options, to_replace[i + 1] - to_replace[i] - 1, p)) % p; current_options--; } return ((int) total); }

Compilation message (stderr)

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: 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 timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...