Submission #1056508

#	Time	Username	Problem	Language	Result	Execution time	Memory
1056508		vnm06	Dungeons Game (IOI21_dungeons)	C++17	37 / 100	772 ms	252712 KiB

dungeons

#include "dungeons.h"
#include<bits/stdc++.h>
#include <vector>

using namespace std;

int N;
vector<int> S, P, W, L;
int ans[3000000][4], br=0;

vector<int> grL[400005], grW[400005];
map<pair<int, int>, int > mp[400005];


void init(int n, std::vector<int> s, std::vector<int> p, std::vector<int> w, std::vector<int> l) 
{
    N=n;
    S=s;
    P=p;
    W=w;
    L=l;
    for(int i=0; i<n; i++)
    {
        grL[L[i]].push_back(i);
        grW[W[i]].push_back(i);
    }
    ans[0][0]=n;
    ans[0][1]=0;
    ans[0][2]=2e8;
    ans[0][3]=0;
    br=1;
    for(int i=0; i<br; i++)
    {
        int v=ans[i][0], be=ans[i][1], en=ans[i][2], dob=ans[i][3];
        int brL=grL[v].size();
        for(int j=0; j<brL; j++)
        {
            int nv=grL[v][j], nbe=be-P[nv], nen=en-P[nv], ndob=dob+P[nv];
            if(nbe<0) nbe=0;
            if(nen>=S[nv]) nen=S[nv]-1;
            if(nen>=nbe)
            {
                ans[br][0]=nv;
                ans[br][1]=nbe;
                ans[br][2]=nen;
                ans[br][3]=ndob;
                br++;
            }
        }
        int brW=grW[v].size();
        for(int j=0; j<brW; j++)
        {
            int nv=grW[v][j], nbe=be-S[nv], nen=en-S[nv], ndob=dob+S[nv];
            if(nbe<S[nv]) nbe=S[nv];
            if(nen>=nbe)
            {
                ans[br][0]=nv;
                ans[br][1]=nbe;
                ans[br][2]=nen;
                ans[br][3]=ndob;
                br++;
            }
        }
    }
    for(int i=0; i<br; i++)
    {
        int v=ans[i][0], be=ans[i][1], en=ans[i][2], dob=ans[i][3];
        mp[v][{be, en}]=dob;
    }
}

long long simulate(int x, int z) 
{
    map<pair<int, int>, int >::iterator it=mp[x].lower_bound({z, 1e9});
    it--;
	return z+(*it).second;
}

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