Submission #1275937

#TimeUsernameProblemLanguageResultExecution timeMemory
1275937LeynaGondola (IOI14_gondola)C++20
100 / 100
20 ms6084 KiB
#include "gondola.h" #include <iostream> #include <vector> #include <algorithm> using namespace std; using ll = long long; int valid(int n, int inputSeqArray[]) { vector<int> inputSeq(n); for (int i=0; i<n; i++) inputSeq[i] = inputSeqArray[i]; int mini = 1e9; int min_idx; for (int i=0; i<n; i++){ if (inputSeq[i] < mini){ mini = inputSeq[i]; min_idx = i; } } int needed_val = mini; for (int i=min_idx; i<n; i++){ if (inputSeq[i] <= n){ if (inputSeq[i] != needed_val) return false; } needed_val++; } for (int i=0; i<min_idx; i++){ if (inputSeq[i] <= n){ if (inputSeq[i] != needed_val) return false; } needed_val++; } sort(inputSeq.begin(), inputSeq.end()); for (int i=1; i<n; i++){ if (inputSeq[i] == inputSeq[i-1]) return false; } return true; } //---------------------- int replacement(int n, int gondolaSeq[], int replacementSeq[]) { vector<int> originalSeq(n); int idx = 0; for (int i=0; i<n; i++){ if (gondolaSeq[i] <= n){ idx = i; break; } } if (gondolaSeq[idx] > n) originalSeq[idx] = 1; else originalSeq[idx] = gondolaSeq[idx]; for (int i=idx+1; i<n; i++){ originalSeq[i] = originalSeq[i-1]+1; if (originalSeq[i] > n) originalSeq[i] -= n; } for (int i=idx-1; i>=0; i--){ originalSeq[i] = originalSeq[i+1]-1; if (originalSeq[i] < 1) originalSeq[i] += n; } //for (int x : originalSeq) cerr << x << " "; //cerr << endl; vector<pair<int, int>> replacedGondolas; int max_val = 0; for (int i=0; i<n; i++){ max_val = max(max_val, gondolaSeq[i]); if (gondolaSeq[i] > n){ replacedGondolas.push_back({gondolaSeq[i], i}); } } sort(replacedGondolas.begin(), replacedGondolas.end()); idx = 0; for (int i=n+1; i<=max_val; i++){ int replace_idx = replacedGondolas[idx].second; replacementSeq[i-(n+1)] = originalSeq[replace_idx]; originalSeq[replace_idx] = i; if (i == replacedGondolas[idx].first) idx++; } return max_val-n; } //---------------------- const ll MOD = 1e9+9; ll power(ll base, ll exp){ ll res = 1; while(exp > 0){ if (exp % 2 == 1) res = (res * base) % MOD; base = (base*base) % MOD; exp /= 2; } return res; } int countReplacement(int n, int inputSeq[]) { bool validSeq = valid(n, inputSeq); if (!validSeq) return 0; ll res = 1; vector<int> replacedGondolas; int max_val = 0; for (int i=0; i<n; i++){ max_val = max(max_val, inputSeq[i]); if (inputSeq[i] > n){ replacedGondolas.push_back(inputSeq[i]); } } sort(replacedGondolas.begin(), replacedGondolas.end()); ll remainingGondolas = replacedGondolas.size(); if (remainingGondolas == n) res *= n; int lastGondola = n; for (int i=0; i<replacedGondolas.size(); i++){ res = (res * power(remainingGondolas, (replacedGondolas[i] - lastGondola - 1))) % MOD; if (res >= MOD) res -= MOD; remainingGondolas--; lastGondola = replacedGondolas[i]; } return res; } /* int idx = 0; for (int i=n+1; i<=max_val; i++){ if (replacedGondolas[idx] == i){ idx++; remainingGondolas--; } else{ res = (res * remainingGondolas) % MOD; } } */
#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...