Submission #1082375

#	Time	Username	Problem	Language	Result	Execution time	Memory
1082375		HappyCapybara	Dungeons Game (IOI21_dungeons)	C++17	25 / 100	1365 ms	2097152 KiB

dungeons

#include "dungeons.h"
#include<bits/stdc++.h>
using namespace std;

#define ll long long

int n;
vector<int> s, p, w, l, ds;
vector<vector<vector<pair<int,ll>>>> v;

void init(int N, vector<int> S, vector<int> P, vector<int> W, vector<int> L){
	n = N;
	s = S;
	p = P;
	w = W;
	l = L;
    for (int i=0; i<n; i++){
        int b = true;
        for (int x : ds){
            if (x == s[i]) b = false;
        }
        if (b) ds.push_back(s[i]);
    }
    ds.push_back(0);
    sort(ds.begin(), ds.end());
    s.push_back(0);
    p.push_back(0);
    w.push_back(n);
    l.push_back(n);
	v.resize(ds.size(), vector<vector<pair<int,ll>>>(n+1, vector<pair<int,ll>>(30)));
    for (int k=0; k<ds.size(); k++){
	    for (int i=0; i<30; i++){
		    for (int j=0; j<=n; j++){
			    if (i == 0){
				    if (ds[k] < s[j] ) v[k][j][i] = {l[j], p[j]};
				    else v[k][j][i] = {w[j], s[j]};
			    }
			    else {
				    v[k][j][i].first = v[k][v[k][j][i-1].first][i-1].first;
				    v[k][j][i].second = v[k][j][i-1].second + v[k][v[k][j][i-1].first][i-1].second;
			    }
		    }
	    }
    }
    /*for (int k=0; k<1; k++){
        for (int i=0; i<n; i++){
            for (int j=0; j<5; j++){
                cout << v[k][i][j].first << " " << v[k][i][j].second << "\n";
            }
            cout << "\n";
        }
    }*/
	return;
}

ll simulate(int x, int z){
	ll y = z;
    int cur = 0;
    while (cur < ds.size()){
	    while ((cur == ds.size()-1 || y < ds[cur+1]) && x != n){
		    int i = 0;
		    while ((cur == ds.size()-1 || y+v[cur][x][i+1].second < ds[cur+1]) && v[cur][x][i].first != n) i++;
            y += v[cur][x][i].second;
		    x = v[cur][x][i].first;
	    }
        cur++;
    }
	return y;
}

Compilation message (stderr)

dungeons.cpp: In function 'void init(int, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
dungeons.cpp:31:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   31 |     for (int k=0; k<ds.size(); k++){
      |                   ~^~~~~~~~~~
dungeons.cpp: In function 'long long int simulate(int, int)':
dungeons.cpp:59:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   59 |     while (cur < ds.size()){
      |            ~~~~^~~~~~~~~~~
dungeons.cpp:60:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   60 |      while ((cur == ds.size()-1 || y < ds[cur+1]) && x != n){
      |              ~~~~^~~~~~~~~~~~~~
dungeons.cpp:62:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   62 |       while ((cur == ds.size()-1 || y+v[cur][x][i+1].second < ds[cur+1]) && v[cur][x][i].first != n) i++;
      |               ~~~~^~~~~~~~~~~~~~

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