oj.uz

답안 #961560

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
961560 2024-04-12T08:08:24 Z Warinchai 던전 (IOI21_dungeons) C++17
13 / 100
 1410 ms 1571860 KB 
#include "dungeons.h"
#include<bits/stdc++.h>
using namespace std;
int lift[50][50][50005];
int mn[50][50][50005];
long long dis[50][50][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<=45;i++){
        int st=(1<<(i-1))+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<=40;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){
        //cerr<<x<<" "<<pow<<"\n";
        if(lv==25)return pow+dis[lv][40][x];
        for(int i=40;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;
}

Subtask #1
0.0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 328 ms 614484 KB Output is correct
2 Correct 72 ms 614580 KB Output is correct
3 Correct 90 ms 652884 KB Output is correct
4 Correct 778 ms 1568876 KB Output is correct
5 Incorrect 98 ms 658944 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #2
0.0 / 26.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 82 ms 639812 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 83 ms 641932 KB Output is correct
2 Correct 813 ms 1570680 KB Output is correct
3 Correct 663 ms 1570784 KB Output is correct
4 Correct 705 ms 1568924 KB Output is correct
5 Correct 710 ms 1568932 KB Output is correct
6 Correct 1086 ms 1570408 KB Output is correct
7 Correct 1159 ms 1570640 KB Output is correct
8 Correct 1035 ms 1570728 KB Output is correct
9 Correct 942 ms 1570680 KB Output is correct
10 Correct 1149 ms 1570388 KB Output is correct
11 Correct 1214 ms 1568844 KB Output is correct
12 Correct 1410 ms 1570600 KB Output is correct
13 Correct 1231 ms 1571860 KB Output is correct

Subtask #4
0.0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 83 ms 641932 KB Output is correct
2 Correct 813 ms 1570680 KB Output is correct
3 Correct 663 ms 1570784 KB Output is correct
4 Correct 705 ms 1568924 KB Output is correct
5 Correct 710 ms 1568932 KB Output is correct
6 Correct 1086 ms 1570408 KB Output is correct
7 Correct 1159 ms 1570640 KB Output is correct
8 Correct 1035 ms 1570728 KB Output is correct
9 Correct 942 ms 1570680 KB Output is correct
10 Correct 1149 ms 1570388 KB Output is correct
11 Correct 1214 ms 1568844 KB Output is correct
12 Correct 1410 ms 1570600 KB Output is correct
13 Correct 1231 ms 1571860 KB Output is correct
14 Incorrect 88 ms 641724 KB Output isn't correct
15 Halted 0 ms 0 KB -

Subtask #5
0.0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 83 ms 641932 KB Output is correct
2 Correct 813 ms 1570680 KB Output is correct
3 Correct 663 ms 1570784 KB Output is correct
4 Correct 705 ms 1568924 KB Output is correct
5 Correct 710 ms 1568932 KB Output is correct
6 Correct 1086 ms 1570408 KB Output is correct
7 Correct 1159 ms 1570640 KB Output is correct
8 Correct 1035 ms 1570728 KB Output is correct
9 Correct 942 ms 1570680 KB Output is correct
10 Correct 1149 ms 1570388 KB Output is correct
11 Correct 1214 ms 1568844 KB Output is correct
12 Correct 1410 ms 1570600 KB Output is correct
13 Correct 1231 ms 1571860 KB Output is correct
14 Incorrect 88 ms 641724 KB Output isn't correct
15 Halted 0 ms 0 KB -

Subtask #6
0.0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 82 ms 639812 KB Output isn't correct
2 Halted 0 ms 0 KB -