Submission #465503

#	Time	Username	Problem	Language	Result	Execution time	Memory
465503		blue	Dungeons Game (IOI21_dungeons)	C++17	Compilation error	0 ms	0 KiB

dungeons

#include "dungeons.h"
#include <vector>
#include <iostream>
#include <cassert>
using namespace std;

const int maxN = 50'000;
const int lgN = 20;
const int lgS = 50;

long long pow2[lgS + 1];
//
int N;
vector<int> S;
vector<int> P;
vector<int> W;
vector<int> L;
//
int nxt[maxN + 1][lgS][lgN]; //dungeon
long long gain[maxN + 1][lgS][lgN];
long long min_change[maxN + 1][lgS][lgN]; //minimum start to end up in different magnitude.

void init(int n, vector<int> s, vector<int> p, vector<int> w, vector<int> l)
{
    pow2[0] = 1;
    for(int e = 1; e <= lgS; e++)
        pow2[e] = 2 * pow2[e-1];

    s.push_back(0);
    p.push_back(0);
    w.push_back(n);
    l.push_back(n);

    N = n;
    S = s;
    P = p;
    W = w;
    L = l;

    for(int i = 0; i <= N; i++)
    {
        for(int k = 0; k < lgS; k++)
        {
            if(s[i] < pow2[k])
            {
                nxt[i][k][0] = w[i];
                gain[i][k][0] = s[i];
                min_change[i][k][0] = pow2[k+1] - gain[i][k][0];
            }
            else if(pow2[k] <= s[i] && s[i] < pow2[k+1])
            {
                nxt[i][k][0] = l[i];
                gain[i][k][0] = p[i];
                min_change[i][k][0] = min(pow2[k+1] - p[i], s[i]);
            }
            else
            {
                nxt[i][k][0] = l[i];
                gain[i][k][0] = p[i];
                min_change[i][k][0] = pow2[k+1] - gain[i][k][0];
            }
        }
    }

    for(int e = 1; e < lgN; e++)
    {
        for(int i = 0; i <= N; i++)
        {
            for(int k = 0; k < lgS; k++)
            {
                nxt[i][k][e] = nxt[ nxt[i][k][e-1] ][k][e-1];
                gain[i][k][e] = gain[i][k][e-1] + gain[ nxt[i][k][e-1] ][k][e-1];
                min_change[i][k][e] = min(min_change[i][k][e-1], min_change[ nxt[i][k][e-1] ][k][e-1] - gain[i][k][e-1]);
            }
        }
    }
}

long long simulate(int x, int z)
{
    int X = x;
    long long Z = z;
    for(int k = 0; k < lgS; k++)
    {
        // cerr << "\n\n\n";
        // cerr << "k = " << k << '\n';
        // cerr << "X = " << X << '\n';
        // cerr << "Z = " << Z << '\n';
        if(pow2[k+1] <= Z) continue;
        // cerr << "entered!\n";
        // cerr << "Z = " << Z << '\n';
        for(int e = lgN - 1; e >= 0; e--)
        {
            // cerr << X << ' ' << Z << ' ' << k << ' ' << e << ' ' << min_change[X][k][e] << ' ' << nxt[X][k][e] << ' ' << gain[X][k][e] << '\n';
            if(Z >= min_change[X][k][e]) continue;
            // cerr << "done!\n";
            Z += gain[X][k][e];
            X = nxt[X][k][e];

            if(X == N) return Z;
        }
        // cerr << "Z = " << Z << '\n';
        assert(pow2[k] <= Z);
        assert(Z < pow2[k+1]);


        if(Z >= S[X])
        {
            Z += S[X];
            X = W[X];
        }
        else
        {
            Z += P[X];
            X = L[X];
        }

        if(X == N) return Z;

        assert(pow2[k+1] <= Z);

        // cerr << "after manual operation, Z = " << Z << '\n';
        // cerr << "X = " << X << '\n';
    }

    return Z;
}

Compilation message (stderr)

dungeons.cpp: In function 'void init(int, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
dungeons.cpp:54:65: error: no matching function for call to 'min(long long int, __gnu_cxx::__alloc_traits<std::allocator<int>, int>::value_type&)'
   54 |                 min_change[i][k][0] = min(pow2[k+1] - p[i], s[i]);
      |                                                                 ^
In file included from /usr/include/c++/10/vector:60,
                 from dungeons.h:1,
                 from dungeons.cpp:1:
/usr/include/c++/10/bits/stl_algobase.h:230:5: note: candidate: 'template<class _Tp> constexpr const _Tp& std::min(const _Tp&, const _Tp&)'
  230 |     min(const _Tp& __a, const _Tp& __b)
      |     ^~~
/usr/include/c++/10/bits/stl_algobase.h:230:5: note:   template argument deduction/substitution failed:
dungeons.cpp:54:65: note:   deduced conflicting types for parameter 'const _Tp' ('long long int' and '__gnu_cxx::__alloc_traits<std::allocator<int>, int>::value_type' {aka 'int'})
   54 |                 min_change[i][k][0] = min(pow2[k+1] - p[i], s[i]);
      |                                                                 ^
In file included from /usr/include/c++/10/vector:60,
                 from dungeons.h:1,
                 from dungeons.cpp:1:
/usr/include/c++/10/bits/stl_algobase.h:278:5: note: candidate: 'template<class _Tp, class _Compare> constexpr const _Tp& std::min(const _Tp&, const _Tp&, _Compare)'
  278 |     min(const _Tp& __a, const _Tp& __b, _Compare __comp)
      |     ^~~
/usr/include/c++/10/bits/stl_algobase.h:278:5: note:   template argument deduction/substitution failed:
dungeons.cpp:54:65: note:   deduced conflicting types for parameter 'const _Tp' ('long long int' and '__gnu_cxx::__alloc_traits<std::allocator<int>, int>::value_type' {aka 'int'})
   54 |                 min_change[i][k][0] = min(pow2[k+1] - p[i], s[i]);
      |                                                                 ^