Submission #442116

#	Time	Username	Problem	Language	Result	Execution time	Memory
442116		daniel920712	Dungeons Game (IOI21_dungeons)	C++17	11 / 100	7018 ms	20132 KiB

dungeons

#include "dungeons.h"
#include <vector>
#include <stdio.h>
#include <set>
using namespace std;
//long long con[50005][35][50005];
//long long nxt[50005][35][50005];
long long how[200005];
vector < long long > fin;
set < long long > tt;
vector < int > S,P,W,L;
void init(int n,vector < int > s,vector < int > p,vector < int > w,vector < int > l)
{
    int i,j,k;
    for(i=0;i<n;i++) tt.insert((long long) s[i]);
    /*for(auto i:tt) fin.push_back(i);

    how[n]=0;

    for(i=n-1;i>=0;i--) how[i]=how[w[i]]+s[i];
    for(k=0;k<(int) fin.size();k++)
    {
        //if(k>10) while(1);
        for(i=0;i<=30;i++)
        {
            nxt[k][i][n]=n;
            con[k][i][n]=0;
        }
        for(i=0;i<n;i++)
        {
            if(fin[k]<=s[i])
            {
                nxt[k][0][i]=(long long) l[i];
                con[k][0][i]=(long long) p[i];
            }
            else
            {
                nxt[k][0][i]=(long long) w[i];
                con[k][0][i]=(long long) s[i];
            }

        }
        for(i=1;i<=30;i++)
        {
            for(j=0;j<n;j++)
            {
                nxt[k][i][j]=nxt[k][i-1][nxt[k][i-1][j]];
                con[k][i][j]=con[k][i-1][j]+con[k][i-1][nxt[k][i-1][j]];
                //printf("%d %d %lld %lld\n",i,j,nxt[i][j],con[i][j]);
            }
        }
    }*/
    S=s;
    P=p;
    W=w;
    L=l;

	return;
}

long long simulate(int x, int z)
{
    long long ans=z;
    //return 0;
    /*long long ans=(long long) z,now=x,i,j;
    for(j=0;j<fin.size();j++)
    {
        if(ans>=fin[j]) continue;
        for(i=30;i>=0;i--)
        {
            if(ans+con[j][i][now]<fin[j])
            {
                //printf("%lld %lld %lld %lld %lld\n",ans,i,now,con[i][now],nxt[i][now]);
                ans+=con[j][i][now];
                now=nxt[j][i][now];
            }
            //printf("%lld %lld %lld\n",i,ans,now);
        }
        ans+=con[j][0][now];
        now=nxt[j][0][now];
    }

    return ans+how[now];*/
    while(x!=S.size())
    {
        if(ans>=S[x])
        {
            ans+=(long long) S[x];
            x=W[x];
        }
        else
        {
            ans+=(long long) P[x];
            x=L[x];
        }
    }
    return ans;


}

Compilation message (stderr)

dungeons.cpp: In function 'void init(int, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
dungeons.cpp:14:11: warning: unused variable 'j' [-Wunused-variable]
   14 |     int i,j,k;
      |           ^
dungeons.cpp:14:13: warning: unused variable 'k' [-Wunused-variable]
   14 |     int i,j,k;
      |             ^
dungeons.cpp: In function 'long long int simulate(int, int)':
dungeons.cpp:84:12: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   84 |     while(x!=S.size())
      |           ~^~~~~~~~~~

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