Submission #799390

#TimeUsernameProblemLanguageResultExecution timeMemory
799390errayGondola (IOI14_gondola)C++17
40 / 100
26 ms5008 KiB
#include "gondola.h" #include <bits/stdc++.h> using namespace std; #ifdef DEBUG #include "/home/ioi/codes/ioi14_d2/debug.h" #else #define debug(...) void(37) #endif template<typename T> vector<T> inverse_fuck(T* a, int N) { vector<T> res(N); for (int i = 0; i < N; ++i) { res[i] = a[i]; } return res; } const int md = int(1e9) + 9; struct Mint { int val = 0; Mint() : val(0) { } template<typename T> Mint(T x) { if (-md <= x && x < md) { val = x; } else { val = x % md; } if (val < 0) { val += md; } } int& operator()() { return val; } Mint& operator+=(Mint x) { if ((val += x.val) > md) { val -= md; } return *this; } Mint& operator-=(Mint x) { if ((val -= x.val) < 0) { val += md; } return *this; } Mint& operator*=(Mint x) { val = int(1LL * val * x.val % md); return *this; } }; Mint operator+(Mint x, Mint y) { return x += y; } Mint operator-(Mint x, Mint y) { return x -= y; } Mint operator*(Mint x, Mint y) { return x *= y; } string to_string(Mint x) { return to_string(x.val); } template<typename T> Mint power(Mint x, T p) { Mint res = 1; while (p > 0) { if (p & 1) { res *= x; } x *= x; p >>= 1; } return res; } int valid(int N, int inputSeq[]) { auto A = inverse_fuck(inputSeq, N); int prev = -1; for (int i = 0; i < N; ++i) { if (A[i] <= N) { if (prev != -1) { if (i - prev != (A[i] - A[prev] + N) % N) { return false; } } prev = i; } } return set<int>(A.begin(), A.end()).size() == A.size(); } //---------------------- int replacement(int N, int inputSeq[], int replacementSeq[]) { auto A = inverse_fuck(inputSeq, N); /* int mn = min_element(A.begin(), A.end()) - A.begin(); //vector<int> cur(N); if (A[mn] <= N) { vector<int> sa(N); for (int i = 0; i < N; ++i) { sa[(A[mn] - 1 + i) % N] = A[(mn + i) % N]; //cur[(mn + i) % N] = i + 1; } swap(A, sa); } */ int mx = max_element(A.begin(), A.end()) - A.begin(); vector<int> pos(A[mx] + 1, -1); for (int i = 0; i < N; ++i) { pos[A[i]] = i; } vector<int> ans; for (int i = N + 1; i <= A[mx]; ++i) { int use = (pos[i] == -1 ? mx : pos[i]); ans.push_back(use); //cur[use] = i; } for (int i = 0; i < int(ans.size()); ++i) { replacementSeq[i] = ans[i] + 1; } return int(ans.size()); } //---------------------- int countReplacement(int N, int inputSeq[]) { auto A = inverse_fuck(inputSeq, N); if (!valid(N, inputSeq)) { return 0; } sort(A.begin(), A.end()); Mint res = 1; int prev = N; for (int i = 0; i < N; ++i) { if (A[i] <= N) { continue; } res *= power(N - i, A[i] - prev - 1); prev = A[i]; } return res(); }
#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...