oj.uz

Submission #1080557

# Submission time Handle Problem Language Result Execution time Memory
1080557 2024-08-29T10:55:38 Z eyalz Magic Show (APIO24_show) C++17
100 / 100
 2 ms 1028 KB 
#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;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 780 KB Correct.
2 Correct 0 ms 784 KB Correct.
3 Correct 0 ms 776 KB Correct.
4 Correct 1 ms 776 KB Correct.
5 Correct 1 ms 1028 KB Correct.
6 Correct 0 ms 776 KB Correct.
7 Correct 0 ms 784 KB Correct.
8 Correct 0 ms 772 KB Correct.
9 Correct 0 ms 776 KB Correct.
10 Correct 0 ms 776 KB Correct.
11 Correct 1 ms 776 KB Correct.
12 Correct 0 ms 776 KB Correct.

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 780 KB Correct.
2 Correct 0 ms 784 KB Correct.
3 Correct 0 ms 776 KB Correct.
4 Correct 1 ms 776 KB Correct.
5 Correct 1 ms 1028 KB Correct.
6 Correct 0 ms 776 KB Correct.
7 Correct 0 ms 784 KB Correct.
8 Correct 0 ms 772 KB Correct.
9 Correct 0 ms 776 KB Correct.
10 Correct 0 ms 776 KB Correct.
11 Correct 1 ms 776 KB Correct.
12 Correct 0 ms 776 KB Correct.
13 Correct 0 ms 776 KB Correct.
14 Correct 0 ms 776 KB Correct.
15 Correct 0 ms 776 KB Correct.
16 Correct 0 ms 776 KB Correct.
17 Correct 0 ms 776 KB Correct.
18 Correct 0 ms 784 KB Correct.
19 Correct 0 ms 776 KB Correct.
20 Correct 1 ms 776 KB Correct.
21 Correct 0 ms 776 KB Correct.
22 Correct 0 ms 776 KB Correct.
23 Correct 0 ms 780 KB Correct.
24 Correct 0 ms 776 KB Correct.

Subtask #3
65.0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 780 KB Correct.
2 Correct 0 ms 784 KB Correct.
3 Correct 0 ms 776 KB Correct.
4 Correct 1 ms 776 KB Correct.
5 Correct 1 ms 1028 KB Correct.
6 Correct 0 ms 776 KB Correct.
7 Correct 0 ms 784 KB Correct.
8 Correct 0 ms 772 KB Correct.
9 Correct 0 ms 776 KB Correct.
10 Correct 0 ms 776 KB Correct.
11 Correct 1 ms 776 KB Correct.
12 Correct 0 ms 776 KB Correct.
13 Correct 0 ms 776 KB Correct.
14 Correct 0 ms 776 KB Correct.
15 Correct 0 ms 776 KB Correct.
16 Correct 0 ms 776 KB Correct.
17 Correct 0 ms 776 KB Correct.
18 Correct 0 ms 784 KB Correct.
19 Correct 0 ms 776 KB Correct.
20 Correct 1 ms 776 KB Correct.
21 Correct 0 ms 776 KB Correct.
22 Correct 0 ms 776 KB Correct.
23 Correct 0 ms 780 KB Correct.
24 Correct 0 ms 776 KB Correct.
25 Correct 0 ms 776 KB Correct.
26 Correct 0 ms 744 KB Correct.
27 Correct 0 ms 776 KB Correct.
28 Correct 1 ms 776 KB Correct.
29 Correct 0 ms 772 KB Correct.
30 Correct 2 ms 776 KB Correct.
31 Correct 0 ms 776 KB Correct.
32 Correct 0 ms 776 KB Correct.
33 Correct 2 ms 724 KB Correct.
34 Correct 1 ms 776 KB Correct.
35 Correct 0 ms 784 KB Correct.
36 Correct 0 ms 776 KB Correct.
37 Correct 0 ms 776 KB Correct.
38 Correct 0 ms 772 KB Correct.
39 Correct 0 ms 772 KB Correct.
40 Correct 2 ms 776 KB Correct.
41 Correct 0 ms 776 KB Correct.
42 Correct 0 ms 776 KB Correct.
43 Correct 1 ms 776 KB Correct.
44 Correct 0 ms 776 KB Correct.