Submission #1080561

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1080561	2024-08-29T10:58:37 Z	eyalz	Magic Show (APIO24_show)	C++17	Compilation error	0 ms	0 KB

Alice

#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;

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;
}

Bob

#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

Alice.cpp:14:12: error: 'd' was not declared in this scope
   14 | int C[N],V[d][d],Y[d];
      |            ^
Alice.cpp:14:15: error: 'd' was not declared in this scope
   14 | int C[N],V[d][d],Y[d];
      |               ^
Alice.cpp:14:20: error: 'd' was not declared in this scope
   14 | int C[N],V[d][d],Y[d];
      |                    ^
Alice.cpp: In function 'vpii Alice()':
Alice.cpp:19:25: error: 'd' was not declared in this scope
   19 |     for(int i = 1; i <= d; ++i)
      |                         ^
Alice.cpp:21:16: error: 'Y' was not declared in this scope
   21 |         C[i] = Y[i-1] = X % i;
      |                ^
Alice.cpp:25:24: error: 'd' was not declared in this scope
   25 |     for(int i = 0; i < d; ++i)
      |                        ^
Alice.cpp:30:13: error: 'V' was not declared in this scope
   30 |             V[i][j] = a;
      |             ^
Alice.cpp:34:24: error: 'd' was not declared in this scope
   34 |     for(int i = 0; i < d; ++i)
      |                        ^
Alice.cpp:37:17: error: 'V' was not declared in this scope
   37 |         int a = V[i][i];
      |                 ^
Alice.cpp:45:9: error: 'Y' was not declared in this scope
   45 |         Y[i] = e * Y[i] % p;
      |         ^
Alice.cpp:55:24: error: 'd' was not declared in this scope
   55 |     for(int i = 0; i < d; ++i)
      |                        ^
Alice.cpp:61:26: error: 'Y' was not declared in this scope
   61 |             r = (r + a * Y[j] % p * j % p) % p;
      |                          ^

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)
      |                    ^~~~