Submission #705264

#TimeUsernameProblemLanguageResultExecution timeMemory
705264ThegeekKnight16Gondola (IOI14_gondola)C++17
45 / 100
47 ms6988 KiB
#include <bits/stdc++.h> #include "gondola.h" using namespace std; const int MOD = 1e9 + 9; const int MAXN = 1e5 + 10; int expect[MAXN]; map<int, int> marc; int mult(long long int a, long long int b) { return ((a * b) % MOD); } int exp(int x, int n) { if (n == 0) return 1; if (n == 1) return x; if (n % 2) return mult(x, exp(x, n-1)); return exp(mult(x, x), n/2); } int valid(int n, int inputSeq[]) { for (int i = 0; i < n; i++) { if (marc[inputSeq[i]]) return 0; marc[inputSeq[i]] = 1; } bool Achei = false; for (int i = 0; i < n; i++) { if (!Achei && inputSeq[i] > n) continue; else if (!Achei && inputSeq[i] <= n) { expect[i] = inputSeq[i]; Achei = true; } else if (Achei) expect[i] = (expect[i-1]+1); if (expect[i] > n) expect[i] -= n; } if (!expect[0]) expect[0] = expect[n-1]+1; if (expect[0] > n) expect[0] -= n; for (int i = 1; i < n && !expect[i]; i++) { expect[i] = expect[i-1]+1; if (expect[i] > n) expect[i] -= n; } for (int i = 0; i < n; i++) { if (inputSeq[i] > n) continue; if (expect[i] != inputSeq[i]) return 0; } return 1; } //---------------------- int replacement(int n, int gondolaSeq[], int replacementSeq[]) { if (!valid(n, gondolaSeq)) return 0; int tam = 0; int atual = n+1; set<pair<int, int> > fora; for (int i = 0; i < n; i++) if (gondolaSeq[i] > n) fora.emplace(expect[i], i); while (!fora.empty()) { replacementSeq[tam++] = fora.begin()->first; int id = fora.begin()->second; fora.erase(fora.begin()); if (atual < gondolaSeq[id]) fora.emplace(atual, id); atual++; } return tam; } //---------------------- int countReplacement(int n, int inputSeq[]) { // cerr << "ABA" << '\n'; if (!valid(n, inputSeq)) return 0; set<int> fora; // cerr << "CABA" << '\n'; for (int i = 0; i < n; i++) if (inputSeq[i] > n) fora.emplace(inputSeq[i]); int atual = n+1; int resp = 1; // cerr << "SABA" << '\n'; while (!fora.empty()) { resp = mult(resp, exp(fora.size(), *fora.begin() - atual)); atual = (*fora.begin()); atual++; fora.erase(fora.begin()); } // cerr << "VABA" << '\n'; return resp; }
#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...