Submission #1080557

#TimeUsernameProblemLanguageResultExecution timeMemory
1080557eyalzMagic Show (APIO24_show)C++17
100 / 100
2 ms1028 KiB
#include"Alice.h" #include<bits/stdc++.h> using namespace std; using llong = long long; using vpii = vector<pair<int,int>>; constexpr int N = 101; constexpr int q = 9; constexpr int s = 25; int Q[q],S[s]; bool I[N]; vpii Alice() { // init for(int i = 0; i < N; ++i) I[i] = false; // get X llong X = setN(N + 1) - 1; // represent X in base N (resulting in q numbers). store in Q. for(int i = 0; i < q; ++i) { Q[i] = X % N; X /= N; } // make a polynomial with coefficents from Q, and calculate it at s points, storing the result in S. // I indicates which numbers are in S. for(int i = 0; i < s; ++i) { int r = 0; int p = 1; for(int f : Q) { r = (r + (p * f) % N) % N; p = p * i % N; } S[i] = r; I[r] = true; } // create tree vpii T; T.reserve(N); for(int i = 0; i < N; ++i) { if(!I[i]) T.push_back({i + 1, S[i%s] + 1}); else T.push_back({i + 1, N + 1}); } return T; }
#include"Bob.h" #include<bits/stdc++.h> using namespace std; using llong = long long; using vpii = vector<pair<int,int>>; constexpr int N = 101; constexpr int q = 9; constexpr int s = 25; int V[q][q], Y[q], S[s]; bool I[N], M[N][s]; llong Bob(vpii T) { // clear arrays for(int i = 0; i < N; ++i) { I[i] = false; for(int j = 0; j < s; ++j) M[i][j] = false; } // find I - which numbers are in S, and M - what indices in S a number is at. for(auto[a,b] : T) { --a; --b; I[b] |= a == N; I[a] |= b == N; if(a != N && b != N) { // if already has a neighbor with this rem, this is an important node. I[b] |= M[b][a%s]; I[a] |= M[a][b%s]; M[a][b%s] = M[b][a%s] = true; } } // use I and M to restore S. -1 indicates the number is unknown. // N and s are picked such that atleast q = logN(maxX-1) numbers are recoverable. for(int m = 0; m < s; ++m) { S[m] = -1; for(int i = 0; i < N; ++i) { if(I[i] && M[i][m]) { S[m] = i; break; } } } // polynomial interpolation over mod N field. // create vandermont matrix (V) and result vector (Y). int c = 0; for(int i = 0; i < s; ++i) { if(c >= q) break; if(S[i] != -1) { int p = 1; for(int j = 0; j < q; ++j) { V[c][j] = p; p = p * i % N; } Y[c] = S[i]; ++c; } } // using elimination, calculate V^-1 * Y to get the vector of the polynomial coefficients, stored in Y as an optimization. for(int i = 0; i < q; ++i) { int e = 1; int a = V[i][i]; // e = inverse of V[i][i] for(int p = N-2; p; p>>=1) { if(p&1) e = e*a%N; a = a*a%N; } //step 1: for(int j = i; j < q; ++j) V[i][j] = e*V[i][j]%N; Y[i] = e*Y[i]%N; //V[i][i] is now 1 //step 2: for(int j = 0; j < q; ++j)if(i != j) { int ej = N - V[j][i]; for(int k = 0; k < q; ++k) V[j][k] = (V[j][k] + ej*V[i][k]%N)%N; Y[j] = (Y[j] + ej*Y[i]%N)%N; } //V[j][i] is now 0 for all j != i. } // restore X through the new Y. llong X = 0; llong a = 1; for(int i = 0; i < q; ++i) { X += a*Y[i]; a *= N; } return X+1; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...