oj.uz

Submission #1080563

# Submission time Handle Problem Language Result Execution time Memory
1080563 2024-08-29T10:59:19 Z eyalz Magic Show (APIO24_show) C++17
5 / 100
 2 ms 788 KB 
#include"Alice.h"
#include<bits/stdc++.h>
using namespace std;
using vi = vector<int>;
using vvi = vector<vi>;
using llong = long long;
using pii = pair<int,int>;
using vpii = vector<pii>;
using vb = vector<bool>;

constexpr int N = 45;
constexpr int p = 23;
constexpr int d = p-1;

int C[N],V[d][d],Y[d];
vpii Alice()
{
    llong X = setN(N) - 1;
    // turn to rep in base factorial: d digits
    for(int i = 1; i <= d; ++i)
    {
        C[i] = Y[i-1] = X % i;
        X /= i;
    }
    // find polynomial
    for(int i = 0; i < d; ++i)
    {
        int a = 1;
        for(int j = 0; j < d; ++j)
        {
            V[i][j] = a;
            a = a * i % p;
        }
    }
    for(int i = 0; i < d; ++i)
    {
        int e = 1;
        int a = V[i][i];
        for(int w = p-2; w; w>>=1)
        {
            if(w&1) e = e * a % p;
            a = a * a % p;
        }
        for(int k = i; k < d; ++k)
            V[i][k] = e * V[i][k] % p;
        Y[i] = e * Y[i] % p;
        for(int j = 0; j < d; ++j)if(i != j)
        {
            int ej = (p - V[j][i]) % p;
            for(int k = 0; k < d; ++k)
                V[j][k] = (V[j][k] + ej * V[i][k] % p) % p;
            Y[j] = (Y[j] + ej * Y[i] % p) % p;
        }
    }
    // evaluate the derivative at d points
    for(int i = 0; i < d; ++i)
    {
        int r = 0;
        int a = 1;
        for(int j = 1; j < d; ++j)
        {
            r = (r + a * Y[j] % p * j % p) % p;
            a = a * i % p;
        }
        C[i+d+1] = r;
    }
    // encode to tree
    vpii T; T.reserve(N-1);
    for(int i = 1; i < N; ++i)
        T.push_back({i+1, C[i]+1});
    return T;
}
#include"Bob.h"
#include<bits/stdc++.h>
using namespace std;
using vi = vector<int>;
using vvi = vector<vi>;
using llong = long long;
using pii = pair<int,int>;
using vpii = vector<pii>;
using vb = vector<bool>;

constexpr int N = 45;
constexpr int p = 23;
constexpr int d = p-1;

int V[d][d], Y[d], P[d];
llong Bob(vpii T)
{
    // sort such that the matrix rows are correctly ordered
    for(int i = 0; i < T.size(); ++i) if(T[i].first < T[i].second) T[i] = {T[i].second, T[i].first};
    sort(T.begin(), T.end());
    // decode tree
    for(int c = 0; auto[a,b]:T)
    {
        if(c >= d) break;
        if(a < b) swap(a,b);
        --a; --b;
        // polynomial value
        if(a <= d)
        {
            a -= 1;
            int f = 1;
            for(int i = 0; i < d; ++i)
            {
                V[c][i] = f;
                f = f * a % p;
            }
        }
        // derivative value
        else
        {
            a -= d+1;
            int f = 1;
            V[c][0] = 0;
            for(int i = 1; i < d; ++i)
            {
                V[c][i] = f * i % p;
                f = f * a % p;
            }
        }
        Y[c] = b;
        ++c;
    }
    // interpolate
    for(int i = 0; i < d; ++i)
    {
        int e = 1;
        int a = V[i][i];
        // need row swap
        if(a == 0)
        {
            // find first good row
            int c = i+1; while(V[c][i] == 0) ++c;
            // swap
            for(int j = 0; j < d; ++j)
                swap(V[i][j], V[c][j]);
            swap(Y[i], Y[c]);
            a = V[i][i];
        }
        // calculate inverse
        for(int w = p-2; w; w >>= 1)
        {
            if(w&1) e = e * a % p;
            a = a * a % p;
        }
        // make leftmost value in row be 1
        for(int k = i; k < d; ++k)
            V[i][k] = e * V[i][k] % p;
        Y[i] = e * Y[i] % p;
        //reduce all values in column to 0
        for(int j = 0; j < d; ++j)if(i != j)
        {
            int ej = (p - V[j][i]) % p;
            for(int k = 0; k < d; ++k)
                V[j][k] = (V[j][k] + ej * V[i][k] % p) % p;
            Y[j] = (Y[j] + ej * Y[i] % p) % p;
        }
    }
    // find the original d values
    for(int i = 0; i < d; ++i)
    {
        int r = 0;
        int a = 1;
        for(int j = 0; j < d; ++j)
        {
            r = (r + a * Y[j] % p) % p;
            a = a * i % p;
        }
        P[i] = r;
    }
    // convert to X
    llong X = 0;
    llong a = 1;
    for(int i = 0; i < d; ++i)
    {
        X += a * P[i];
        a *= (i+1);
    }
    return X+1;
}

Compilation message

Bob.cpp: In function 'llong Bob(vpii)':
Bob.cpp:19:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   19 |     for(int i = 0; i < T.size(); ++i) if(T[i].first < T[i].second) T[i] = {T[i].second, T[i].first};
      |                    ~~^~~~~~~~~~
Bob.cpp:22:20: warning: range-based 'for' loops with initializer only available with '-std=c++2a' or '-std=gnu++2a'
   22 |     for(int c = 0; auto[a,b]:T)
      |                    ^~~~

Subtask #1
5.0 / 5.0

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

Subtask #2
0.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 776 KB Correct.
2 Correct 0 ms 784 KB Correct.
3 Correct 0 ms 788 KB Correct.
4 Correct 0 ms 780 KB Correct.
5 Correct 1 ms 784 KB Correct.
6 Correct 0 ms 776 KB Correct.
7 Correct 0 ms 776 KB Correct.
8 Correct 0 ms 784 KB Correct.
9 Correct 0 ms 776 KB Correct.
10 Correct 2 ms 776 KB Correct.
11 Correct 0 ms 776 KB Correct.
12 Correct 0 ms 776 KB Correct.
13 Incorrect 1 ms 776 KB Incorrect answer.
14 Halted 0 ms 0 KB -

Subtask #3
0.0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 776 KB Correct.
2 Correct 0 ms 784 KB Correct.
3 Correct 0 ms 788 KB Correct.
4 Correct 0 ms 780 KB Correct.
5 Correct 1 ms 784 KB Correct.
6 Correct 0 ms 776 KB Correct.
7 Correct 0 ms 776 KB Correct.
8 Correct 0 ms 784 KB Correct.
9 Correct 0 ms 776 KB Correct.
10 Correct 2 ms 776 KB Correct.
11 Correct 0 ms 776 KB Correct.
12 Correct 0 ms 776 KB Correct.
13 Incorrect 1 ms 776 KB Incorrect answer.
14 Halted 0 ms 0 KB -