This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#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 time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |