oj.uz

Submission #442113

# Submission time Handle Problem Language Result Execution time Memory
442113 2021-07-07T07:17:57 Z daniel920712 Dungeons Game (IOI21_dungeons) C++17
25 / 100
 684 ms 748788 KB 
#include "dungeons.h"
#include <vector>
#include <stdio.h>
#include <set>
using namespace std;
long long con[15][35][50005];
long long nxt[15][35][50005];
long long how[200005];
vector < long long > fin;
set < long long > tt;
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]);
            }
        }
    }

	return;
}

long long simulate(int x, int 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];


}

Compilation message

dungeons.cpp: In function 'long long int simulate(int, int)':
dungeons.cpp:60:14: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   60 |     for(j=0;j<fin.size();j++)
      |             ~^~~~~~~~~~~

Subtask #1
0.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 460 KB Output is correct
2 Correct 2 ms 3256 KB Output is correct
3 Correct 8 ms 12876 KB Output is correct
4 Runtime error 684 ms 743956 KB Execution killed with signal 11
5 Halted 0 ms 0 KB -

Subtask #2
0.0 / 26.0

# Verdict Execution time Memory Grader output
1 Runtime error 49 ms 24172 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1164 KB Output is correct
2 Correct 73 ms 27376 KB Output is correct
3 Correct 81 ms 27496 KB Output is correct
4 Correct 57 ms 27324 KB Output is correct
5 Correct 57 ms 27344 KB Output is correct
6 Correct 95 ms 27332 KB Output is correct
7 Correct 98 ms 27332 KB Output is correct
8 Correct 62 ms 27324 KB Output is correct
9 Correct 65 ms 27328 KB Output is correct
10 Correct 56 ms 27332 KB Output is correct
11 Correct 73 ms 27328 KB Output is correct
12 Correct 157 ms 27336 KB Output is correct
13 Correct 138 ms 27332 KB Output is correct

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1164 KB Output is correct
2 Correct 73 ms 27376 KB Output is correct
3 Correct 81 ms 27496 KB Output is correct
4 Correct 57 ms 27324 KB Output is correct
5 Correct 57 ms 27344 KB Output is correct
6 Correct 95 ms 27332 KB Output is correct
7 Correct 98 ms 27332 KB Output is correct
8 Correct 62 ms 27324 KB Output is correct
9 Correct 65 ms 27328 KB Output is correct
10 Correct 56 ms 27332 KB Output is correct
11 Correct 73 ms 27328 KB Output is correct
12 Correct 157 ms 27336 KB Output is correct
13 Correct 138 ms 27332 KB Output is correct
14 Correct 3 ms 3532 KB Output is correct
15 Correct 123 ms 75976 KB Output is correct
16 Correct 136 ms 100216 KB Output is correct
17 Correct 128 ms 124484 KB Output is correct
18 Correct 171 ms 124504 KB Output is correct
19 Correct 240 ms 124484 KB Output is correct
20 Correct 148 ms 76000 KB Output is correct
21 Correct 198 ms 100164 KB Output is correct
22 Correct 122 ms 51700 KB Output is correct
23 Correct 193 ms 100164 KB Output is correct
24 Correct 261 ms 75928 KB Output is correct

Subtask #5
0.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1164 KB Output is correct
2 Correct 73 ms 27376 KB Output is correct
3 Correct 81 ms 27496 KB Output is correct
4 Correct 57 ms 27324 KB Output is correct
5 Correct 57 ms 27344 KB Output is correct
6 Correct 95 ms 27332 KB Output is correct
7 Correct 98 ms 27332 KB Output is correct
8 Correct 62 ms 27324 KB Output is correct
9 Correct 65 ms 27328 KB Output is correct
10 Correct 56 ms 27332 KB Output is correct
11 Correct 73 ms 27328 KB Output is correct
12 Correct 157 ms 27336 KB Output is correct
13 Correct 138 ms 27332 KB Output is correct
14 Correct 3 ms 3532 KB Output is correct
15 Correct 123 ms 75976 KB Output is correct
16 Correct 136 ms 100216 KB Output is correct
17 Correct 128 ms 124484 KB Output is correct
18 Correct 171 ms 124504 KB Output is correct
19 Correct 240 ms 124484 KB Output is correct
20 Correct 148 ms 76000 KB Output is correct
21 Correct 198 ms 100164 KB Output is correct
22 Correct 122 ms 51700 KB Output is correct
23 Correct 193 ms 100164 KB Output is correct
24 Correct 261 ms 75928 KB Output is correct
25 Runtime error 647 ms 748788 KB Execution killed with signal 11
26 Halted 0 ms 0 KB -

Subtask #6
0.0 / 11.0

# Verdict Execution time Memory Grader output
1 Runtime error 49 ms 24172 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -