oj.uz

답안 #961795

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
961795 2024-04-12T12:58:11 Z Warinchai 던전 (IOI21_dungeons) C++17
13 / 100
 1410 ms 1082900 KB 
#include "dungeons.h"
#include<bits/stdc++.h>
using namespace std;
int lift[26][26][50005];
int mn[26][26][50005];
long long dis[26][26][50005];
long long inf=1e18+7;
int N;
vector<int>W;
vector<int>S;
vector<int>L;
vector<int>P;
int X=0;
void init(int n,vector<int> s,vector<int> p,vector<int> w,vector<int> l) {
    N=n;
    S=s;
    W=w;
    L=l;
    P=p;
    //cerr<<"work\n";
    for(int i=0;i<=25;i++){
        int st=(1<<(i-1))+1;
        if(i==0)st=1;
        int en=(1<<i);
        for(int j=0;j<n;j++){
            if(s[j]>en)lift[i][0][j]=l[j],mn[i][0][j]=inf,dis[i][0][j]=p[j];
            else if(s[j]>=st)lift[i][0][j]=l[j],mn[i][0][j]=s[j],dis[i][0][j]=p[j];
            else lift[i][0][j]=w[j],mn[i][0][j]=inf,dis[i][0][j]=s[j];
        }
        lift[i][0][n]=n;
        mn[i][0][n]=0;
        for(int j=1;j<=25;j++){
            for(int k=0;k<=n;k++){
                //cerr<<i<<" "<<j<<" "<<k<<"\n";
                lift[i][j][k]=lift[i][j-1][lift[i][j-1][k]];
                dis[i][j][k]=dis[i][j-1][k]+dis[i][j-1][lift[i][j-1][k]];
                X=mn[i][j-1][lift[i][j-1][k]]-dis[i][j-1][k];
                if(dis[i][j-1][k]>mn[i][j-1][lift[i][j-1][k]])mn[i][j][k]=0;
                else mn[i][j][k]=min(mn[i][j-1][k],X);
            }
        }
    }
    //cerr<<"work\n";
	return;
}
 
long long simulate(int x, int z) {
    //cerr<<"work\n";
    long long c=0,lv=0;
    long long pow=z;
    /*while(pow>(1<<c)){
        lv=c;
        c++;
    }*/
    //cerr<<x<<"\n";
    //cerr<<lv<<"\n";
    while(1){
        assert(pow >0);
        //cerr<<x<<" "<<pow<<"\n";
        if(lv==25)return pow+dis[lv][25][x];
        for(int i=25;i>=0;i--){
            //cerr<<i<<" "<<lv<<" "<<x<<"\n";
            if(pow<mn[lv][i][x]&&pow+dis[lv][i][x]<=(1<<lv))pow+=dis[lv][i][x],x=lift[lv][i][x];
        }
        //cerr<<x<<" "<<pow<<"\n\n";
        if(x==N)break;
        if(pow>=S[x])pow+=S[x],x=W[x];
        else {
            pow+=P[x];
            x=L[x];
        }
        lv++;
    }
	return pow;
}

Compilation message

dungeons.cpp: In function 'long long int simulate(int, int)':
dungeons.cpp:49:15: warning: unused variable 'c' [-Wunused-variable]
   49 |     long long c=0,lv=0;
      |               ^

Subtask #1
0.0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 60 ms 124496 KB Output is correct
2 Correct 17 ms 126544 KB Output is correct
3 Correct 25 ms 140944 KB Output is correct
4 Correct 303 ms 532796 KB Output is correct
5 Incorrect 24 ms 142792 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #2
0.0 / 26.0

# 결과 실행 시간 메모리 Grader output
1 Correct 20 ms 132700 KB Output is correct
2 Runtime error 1410 ms 1082900 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #3
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 25 ms 144468 KB Output is correct
2 Correct 339 ms 534344 KB Output is correct
3 Correct 791 ms 534628 KB Output is correct
4 Correct 725 ms 533892 KB Output is correct
5 Correct 675 ms 533700 KB Output is correct
6 Correct 692 ms 534084 KB Output is correct
7 Correct 678 ms 533844 KB Output is correct
8 Correct 598 ms 533688 KB Output is correct
9 Correct 261 ms 533772 KB Output is correct
10 Correct 636 ms 533516 KB Output is correct
11 Correct 723 ms 533844 KB Output is correct
12 Correct 839 ms 534080 KB Output is correct
13 Correct 750 ms 533936 KB Output is correct

Subtask #4
0.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 25 ms 144468 KB Output is correct
2 Correct 339 ms 534344 KB Output is correct
3 Correct 791 ms 534628 KB Output is correct
4 Correct 725 ms 533892 KB Output is correct
5 Correct 675 ms 533700 KB Output is correct
6 Correct 692 ms 534084 KB Output is correct
7 Correct 678 ms 533844 KB Output is correct
8 Correct 598 ms 533688 KB Output is correct
9 Correct 261 ms 533772 KB Output is correct
10 Correct 636 ms 533516 KB Output is correct
11 Correct 723 ms 533844 KB Output is correct
12 Correct 839 ms 534080 KB Output is correct
13 Correct 750 ms 533936 KB Output is correct
14 Correct 43 ms 350032 KB Output is correct
15 Incorrect 365 ms 534068 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #5
0.0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 25 ms 144468 KB Output is correct
2 Correct 339 ms 534344 KB Output is correct
3 Correct 791 ms 534628 KB Output is correct
4 Correct 725 ms 533892 KB Output is correct
5 Correct 675 ms 533700 KB Output is correct
6 Correct 692 ms 534084 KB Output is correct
7 Correct 678 ms 533844 KB Output is correct
8 Correct 598 ms 533688 KB Output is correct
9 Correct 261 ms 533772 KB Output is correct
10 Correct 636 ms 533516 KB Output is correct
11 Correct 723 ms 533844 KB Output is correct
12 Correct 839 ms 534080 KB Output is correct
13 Correct 750 ms 533936 KB Output is correct
14 Correct 43 ms 350032 KB Output is correct
15 Incorrect 365 ms 534068 KB Output isn't correct
16 Halted 0 ms 0 KB -

Subtask #6
0.0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 20 ms 132700 KB Output is correct
2 Runtime error 1410 ms 1082900 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -