oj.uz

Submission #437266

# Submission time Handle Problem Language Result Execution time Memory
437266 2021-06-26T06:22:42 Z errorgorn Dungeons Game (IOI21_dungeons) C++17
63 / 100
 4463 ms 926144 KB 
#include "dungeons.h"

#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define ii pair<ll,ll>
#define fi first
#define se second

#define puf push_front
#define pof pop_front
#define pub push_back
#define pob pop_back

#define rep(x,s,e) for (auto x=s-(s>e);x!=e-(s>e);s<e?x++:x--)
#define all(x) (x).begin(),(x).end()
#define sz(x) (int) (x).size()

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

int n;
ll win_s[50005];
ll lose_s[50005];
ll win_n[50005];
ll lose_n[50005];

struct edge{
  int to;
  ll sum;
  ll mx; //we cant have more strength or we will overshoot
};

vector<ll> ds;
edge tkd[28][50005][28];

void init(int N, std::vector<int> s, std::vector<int> p, std::vector<int> w, std::vector<int> l) {
  n=N;

  rep(x,0,n) win_s[x]=s[x];
  rep(x,0,n) lose_s[x]=p[x];
  rep(x,0,n) win_n[x]=w[x];
  rep(x,0,n) lose_n[x]=l[x];

  for (int x=1;x<2e7;x<<=1) ds.pub(x); //start of bueket sizes
  ds.pub(1e18);

  //for (auto &it:ds) cout<<it<<" "; cout<<endl;

  memset(tkd,-1,sizeof(tkd));

  rep(i,0,sz(ds)-1){
    rep(x,0,n){
      if (win_s[x]<ds[i]){ //cfm will win
        tkd[i][x][0]=edge({win_n[x],win_s[x],(ll)1e18});
      }
      else if (win_s[x]<ds[i+1]){ //by default, we lose, but if we win we must stop!
        tkd[i][x][0]=edge({lose_n[x],lose_s[x],win_s[x]});
      }
      else{ //cfm will lose
        tkd[i][x][0]=edge({lose_n[x],lose_s[x],(ll)1e18});
      }
    }

    rep(y,0,27){
      rep(x,0,n){
        int temp=tkd[i][x][y].to;

        if (temp==-1 || tkd[i][temp][y].to==-1) continue;

        edge res=edge({
          tkd[i][temp][y].to,
          tkd[i][x][y].sum+tkd[i][temp][y].sum,
          min(tkd[i][x][y].mx,tkd[i][temp][y].mx-tkd[i][x][y].sum)
        });

        tkd[i][x][y+1]=res;
      }
    }
  }
}

long long simulate(int CURR, int S) {
  ll curr=CURR,s=S;

  rep(x,0,sz(ds)-1){
    //when we traverse a edge we cannot overshoot over some guy whos in our bucket
    //also sum must be contained in the bucket

    rep(y,28,0){
      if (tkd[x][curr][y].to!=-1 && s+tkd[x][curr][y].sum<ds[x+1] && s<tkd[x][curr][y].mx){
        tie(curr,s)=ii(tkd[x][curr][y].to,s+tkd[x][curr][y].sum);
      }
    }

    //cout<<"debug: "<<curr<<" "<<s<<endl;

    if (curr==n) break;

    //manually do extra one
    if (win_s[curr]<=s){
      s+=win_s[curr];
      curr=win_n[curr];
    }
    else{
      s+=lose_s[curr];
      curr=lose_n[curr];
    }
  }

  return s;

}

Compilation message

dungeons.cpp: In function 'void init(int, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
dungeons.cpp:55:35: warning: narrowing conversion of 'win_n[x]' from 'long long int' to 'int' [-Wnarrowing]
   55 |         tkd[i][x][0]=edge({win_n[x],win_s[x],(ll)1e18});
      |                            ~~~~~~~^
dungeons.cpp:58:36: warning: narrowing conversion of 'lose_n[x]' from 'long long int' to 'int' [-Wnarrowing]
   58 |         tkd[i][x][0]=edge({lose_n[x],lose_s[x],win_s[x]});
      |                            ~~~~~~~~^
dungeons.cpp:61:36: warning: narrowing conversion of 'lose_n[x]' from 'long long int' to 'int' [-Wnarrowing]
   61 |         tkd[i][x][0]=edge({lose_n[x],lose_s[x],(ll)1e18});
      |                            ~~~~~~~~^

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 482 ms 920936 KB Output is correct
2 Correct 448 ms 920824 KB Output is correct
3 Correct 435 ms 921040 KB Output is correct
4 Correct 1146 ms 924064 KB Output is correct
5 Correct 471 ms 921052 KB Output is correct
6 Correct 1127 ms 924100 KB Output is correct

Subtask #2
0.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 431 ms 920976 KB Output is correct
2 Runtime error 220 ms 14016 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 438 ms 920992 KB Output is correct
2 Correct 1359 ms 924852 KB Output is correct
3 Correct 1708 ms 924844 KB Output is correct
4 Correct 1755 ms 924880 KB Output is correct
5 Correct 1769 ms 924856 KB Output is correct
6 Correct 1794 ms 924852 KB Output is correct
7 Correct 1894 ms 924860 KB Output is correct
8 Correct 2154 ms 924868 KB Output is correct
9 Correct 1295 ms 924844 KB Output is correct
10 Correct 2111 ms 925036 KB Output is correct
11 Correct 2372 ms 925048 KB Output is correct
12 Correct 4463 ms 925044 KB Output is correct
13 Correct 3984 ms 925084 KB Output is correct

Subtask #4
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 438 ms 920992 KB Output is correct
2 Correct 1359 ms 924852 KB Output is correct
3 Correct 1708 ms 924844 KB Output is correct
4 Correct 1755 ms 924880 KB Output is correct
5 Correct 1769 ms 924856 KB Output is correct
6 Correct 1794 ms 924852 KB Output is correct
7 Correct 1894 ms 924860 KB Output is correct
8 Correct 2154 ms 924868 KB Output is correct
9 Correct 1295 ms 924844 KB Output is correct
10 Correct 2111 ms 925036 KB Output is correct
11 Correct 2372 ms 925048 KB Output is correct
12 Correct 4463 ms 925044 KB Output is correct
13 Correct 3984 ms 925084 KB Output is correct
14 Correct 458 ms 921040 KB Output is correct
15 Correct 1531 ms 925000 KB Output is correct
16 Correct 1322 ms 925044 KB Output is correct
17 Correct 1996 ms 925044 KB Output is correct
18 Correct 1837 ms 925152 KB Output is correct
19 Correct 1816 ms 925040 KB Output is correct
20 Correct 1869 ms 925048 KB Output is correct
21 Correct 1979 ms 925044 KB Output is correct
22 Correct 1957 ms 925100 KB Output is correct
23 Correct 2658 ms 925048 KB Output is correct
24 Correct 3046 ms 925048 KB Output is correct

Subtask #5
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 438 ms 920992 KB Output is correct
2 Correct 1359 ms 924852 KB Output is correct
3 Correct 1708 ms 924844 KB Output is correct
4 Correct 1755 ms 924880 KB Output is correct
5 Correct 1769 ms 924856 KB Output is correct
6 Correct 1794 ms 924852 KB Output is correct
7 Correct 1894 ms 924860 KB Output is correct
8 Correct 2154 ms 924868 KB Output is correct
9 Correct 1295 ms 924844 KB Output is correct
10 Correct 2111 ms 925036 KB Output is correct
11 Correct 2372 ms 925048 KB Output is correct
12 Correct 4463 ms 925044 KB Output is correct
13 Correct 3984 ms 925084 KB Output is correct
14 Correct 458 ms 921040 KB Output is correct
15 Correct 1531 ms 925000 KB Output is correct
16 Correct 1322 ms 925044 KB Output is correct
17 Correct 1996 ms 925044 KB Output is correct
18 Correct 1837 ms 925152 KB Output is correct
19 Correct 1816 ms 925040 KB Output is correct
20 Correct 1869 ms 925048 KB Output is correct
21 Correct 1979 ms 925044 KB Output is correct
22 Correct 1957 ms 925100 KB Output is correct
23 Correct 2658 ms 925048 KB Output is correct
24 Correct 3046 ms 925048 KB Output is correct
25 Correct 1188 ms 924284 KB Output is correct
26 Correct 1449 ms 924956 KB Output is correct
27 Correct 1417 ms 925060 KB Output is correct
28 Correct 1405 ms 925056 KB Output is correct
29 Correct 1409 ms 925048 KB Output is correct
30 Correct 1900 ms 925052 KB Output is correct
31 Correct 1966 ms 925864 KB Output is correct
32 Correct 2293 ms 925904 KB Output is correct
33 Correct 1917 ms 926144 KB Output is correct
34 Correct 2750 ms 925988 KB Output is correct
35 Correct 1848 ms 925900 KB Output is correct

Subtask #6
0.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 431 ms 920976 KB Output is correct
2 Runtime error 220 ms 14016 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -