Submission #499201

#	Time	Username	Problem	Language	Result	Execution time	Memory
499201		blue	Dungeons Game (IOI21_dungeons)	C++17	0 / 100	1318 ms	2097156 KiB

dungeons

#include "dungeons.h"
#include <vector>
#include <cassert>
#include <iostream>
using namespace std;
 
const int maxN = 400'000;
const int logN = 27;
const int logS = 30;
 
int N;
vector<int> S;
vector<int> P;
vector<int> W;
vector<int> L;
 
//int nxt[1+maxN][logS][logN];
//int gain[1+maxN][logS][logN];
//int min_change[1+maxN][logS][logN]; //i, k, e
int*** nxt;
int*** gain;
int*** min_change;
 
const int logMX = 27;
long long pow4[1+logMX];
 
vector<long long> winscore(1+maxN, 0LL);
 
void tle_assert(bool b)
{
    if(!b) while(1);
}
 
void init(int n, vector<int> s, vector<int> p, vector<int> w, vector<int> l)
{
  	nxt = new int**[1+maxN];
    gain = new int**[1+maxN];
    min_change = new int**[1+maxN];
    for(int i = 0; i <= maxN; i++)
    {	
      nxt[i] = new int*[logS];
      gain[i] = new int*[logS];
      min_change[i] = new int*[logS];
      for(int j = 0; j < logS; j++)
      {
        nxt[i][j] = new int[logN];
        gain[i][j] = new int[logN];
        min_change[i][j] = new int[logN];
     
      }
	}
  
    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;
 
    pow4[0] = 1;
    for(int e = 1; e <= logMX; e++)
        pow4[e] = 4 * pow4[e-1];
 
 
    for(int i = 0; i <= N; i++)
    {
        for(int k = 0; k < logS; k++)
        {
            if(s[i] < pow4[k])
            {
                nxt[i][k][0] = w[i];
                gain[i][k][0] = s[i];
                min_change[i][k][0] = pow4[k+1] - gain[i][k][0];
            }
            else if(pow4[k] <= s[i] && s[i] < pow4[k+1])
            {
                nxt[i][k][0] = l[i];
                gain[i][k][0] = p[i];
                min_change[i][k][0] = min(pow4[k+1] - p[i], (long long)s[i]);
            }
            else if(pow4[k] < s[i])
            {
                nxt[i][k][0] = l[i];
                gain[i][k][0] = p[i];
                min_change[i][k][0] = pow4[k+1] - gain[i][k][0];
            }
        }
    }
 
    for(int e = 1; e < logN; e++)
    {
        for(int i = 0; i <= N; i++)
        {
            for(int k = 0; k < logS; 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]);
            }
        }
    }
 
    for(int i = N-1; i >= 0; i--)
        winscore[i] = winscore[ W[i] ] + S[i];
 
    // for(int i = 0; i <= N; i++) cerr << winscore[i] << ' ';
    // cerr << '\n';
 
    // for(int k = 0; k < logS; k++)
    // {
    //     for(int e = 0; e < logN; e++)
    //     {
    //         cerr << nxt[N][k][e] << ' ';
    //
    //     }
    //     cerr << '\n';
    // }
    // cerr << '\n';
}
 
long long simulate(int x, int z)
{
    // cerr << "\n\n\n\n";
    // cerr << "simulating " << x << ' ' << z << '\n';
    int X = x;
    long long Z = z;
    for(int k = 0; k < logS; k++)
    {
        for(int T = 1; T <= 3; T++)
        {
            if(pow4[k+1] <= Z) continue;
 
            for(int e = logN - 1; e >= 0; e--)
            {
                if(Z >= min_change[X][k][e]) continue;
                Z += gain[X][k][e];
                X = nxt[X][k][e];
                if(X == N) break;
            }
            if(X == N) break;
 
            if(Z >= S[X])
            {
                Z += S[X];
                X = W[X];
            }
            else
            {
                Z += P[X];
                X = L[X];
            }
            if(X == N) break;
        }
    }
    // cerr << "Z = " << Z << '\n';
    // cerr << "ending X = " << X << '\n';
 
    Z += winscore[X];
 
    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:73:29: warning: iteration 28 invokes undefined behavior [-Waggressive-loop-optimizations]
   73 |             if(s[i] < pow4[k])
      |                       ~~~~~~^
dungeons.cpp:71:26: note: within this loop
   71 |         for(int k = 0; k < logS; k++)
      |                        ~~^~~~~~
dungeons.cpp: In function 'long long int simulate(int, int)':
dungeons.cpp:135:24: warning: iteration 27 invokes undefined behavior [-Waggressive-loop-optimizations]
  135 |             if(pow4[k+1] <= Z) continue;
      |                ~~~~~~~~^
dungeons.cpp:131:22: note: within this loop
  131 |     for(int k = 0; k < logS; k++)
      |                    ~~^~~~~~

• Subtask 1: 0 / 11
• Subtask 2: 0 / 26
• Subtask 3: 0 / 13
• Subtask 4: 0 / 12
• Subtask 5: 0 / 27
• Subtask 6: 0 / 11