oj.uz

Submission #820058

# Submission time Handle Problem Language Result Execution time Memory
820058 2023-08-10T18:37:43 Z lollipop Dungeons Game (IOI21_dungeons) C++17
50 / 100
 7000 ms 586000 KB 
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/rope>
//#define ll long long
#define int long long
#define pb push_back
#define s second
#define f first
#define pf push_front
#define inf 1000000000000000
#define bitebi __builtin_popcountll
#define FOR( i , n ) for( int i = 0 ; i < n ; i ++ )
#define YES cout <<"YES\n"
#define NO cout << "NO\n"
#define debug cout << "Here Fine" << endl ;
#define pr pair < int , int >
#define fbo find_by_order // returns iterator
#define ook order_of_key // returns strictly less numbers than key
using namespace std ;
#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,fma")
using namespace __gnu_pbds;
using namespace __gnu_cxx;
#define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>
const double Pi=acos(-1.0);
const double EPS=1E-8;
const int mod =  1000000007 ;
const int mod1 = 998244353 ;
const int N = 4e5 + 10 ;
//mt19937 R(time(0));
map < string , int > ma , ma1 ;

#include "dungeons.h"

int tt = 0 ; 
vector < signed > S , P , W , L ;
int nn , xx[ 30 ] ;
pair < int , int > clos_lose[ N ][ 30 ] , clos_win[ N ][ 30 ] ; 
int at_w[ N ][ 30 ] , at_l[ N ][ 30 ] ; 
void init(signed n, vector<signed> s, vector<signed> p, vector<signed> w, vector<signed> l){
  xx[ 0 ] = 1 ; for( int j = 1 ; j < 30 ; j ++ ) xx[ j ] = xx[ j - 1 ] * 2 ;
  nn = n ; S = s ; P = p ; W = w ; L = l ;
    // precalculate wins 
// pirveli min ramdeni minda iyos, meore ramdenit mizrdis anu s[ i ] ebis jami 
      for( int i = 0 ; i < 30 ; i ++ ){
        for( int j = nn ; j >= 0 ; j -- ){
         if( j == nn ){
          clos_lose[ j ][ i ] = { 0 , 0 } ;
          at_w[ j ][ i ] = nn + 1 ;
          continue ; 
        }
        int mxx = s[ j ] ; 
        int sm = s[ j ] ;
        int pos = W[ j ] ;
        if( i != 0 ){
          mxx = max( mxx , clos_lose[ j ][ i - 1 ].f ) ;
          sm = clos_lose[ j ][ i - 1 ].s ;
          pos = at_w[ j ][ i - 1 ] ;
          if( pos != nn + 1 ){
            int cur = clos_lose[ pos ][ i - 1 ].f ;
            cur = cur - sm ;
            mxx = max( mxx , cur ) ;
            sm = sm + clos_lose[ pos ][ i - 1 ].s ;
            pos = at_w[ pos ][ i - 1 ] ;
          }
        }
        clos_lose[ j ][ i ] = { mxx , sm } ; 
        at_w[ j ][ i ] = pos ; 
      }
    }

    // now close win
      for( int i = 0 ; i < 30 ; i ++ ){
        for( int j = nn ; j >= 0 ; j -- ){
        if( j == nn ){
          clos_win[ j ][ i ] = { 0 , 0 } ;
          at_l[ j ][ i ] = nn + 1 ;
          continue ; 
        }
        int mnn = s[ j ] - 1 ; 
        int sm = p[ j ] ;
        int pos = L[ j ] ;
        if( i != 0 ){
          mnn = min( mnn , clos_win[ j ][ i - 1 ].f ) ;
          sm = clos_win[ j ][ i - 1 ].s ;
          pos = at_l[ j ][ i - 1 ] ;
          if( pos != nn + 1 ){
            int cur = clos_win[ pos ][ i - 1 ].f ;
            cur = cur - sm ;
            mnn = min( mnn , cur ) ;
            sm = sm + clos_win[ pos ][ i - 1 ].s ;
            pos = at_l[ pos ][ i - 1 ] ;
          }
        }
        clos_win[ j ][ i ] = { mnn , sm } ; 
        at_l[ j ][ i ] = pos ; 
      }
    }  

}
int titu = 0 ;
int get_2( int x , int z , int tp ){
   if( tp == 1 ){
     for( int j = 29 ; j >= 0 ; j -- ){
     if( clos_win[ x ][ j ].f >= z ){
       z = z + clos_win[ x ][ j ].s ;
       x = at_l[ x ][ j ] ;
     }
    }
   return get_2( x , z , 0 ) ; 
   }

   if( clos_lose[ x ][ 29 ].f <= z ){
     return ( z + clos_lose[ x ][ 29 ].s ) ;
   }
   // find the first one to whom this looses, you get doubled when you lose
   // so it happens at mos 24 times, that fits into the Time limit
   for( int j = 29 ; j >= 0 ; j -- ){
     if( clos_lose[ x ][ j ].f <= z ){
       z = z + clos_lose[ x ][ j ].s ;
       x = at_w[ x ][ j ] ;
     }
   }
   return get_2( x , z , 1 ) ;
}
long long simulate(signed x, signed z){
     return get_2( x , z , 0 ) ;
}



// static signed n, q;
// static std::vector<signed> s, p, z;
// static std::vector<signed> w, l, x;
// static std::vector<long long> answer;

// signed main() {
// 	assert(scanf("%d %d", &n, &q) == 2);
// 	s.resize(n);
// 	p.resize(n);
// 	w.resize(n);
// 	l.resize(n);
//     x.resize(q);
//     z.resize(q);
//     answer.resize(q);

// 	for (int i = 0; i < n; i++) {
// 		assert(scanf("%d", &s[i]) == 1);
// 	}
// 	for (int i = 0; i < n; i++) {
// 		assert(scanf("%d", &p[i]) == 1);
// 	}
// 	for (int i = 0; i < n; i++) {
// 		assert(scanf("%d", &w[i]) == 1);
// 	}
// 	for (int i = 0; i < n; i++) {
// 		assert(scanf("%d", &l[i]) == 1);
// 	}


//     init(n, s, p, w, l);

//     for (int i = 0; i < q; i++) {
// 		assert(scanf("%d %d", &x[i], &z[i]) == 2);
// 		answer[i] = simulate(x[i], z[i]);
//     }
//     fclose(stdin);

//     for (int i = 0; i < q; i++) {
//         printf("%lld\n", answer[i]);
//     }
//     return 0;
// }

Subtask #1
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 3 ms 3156 KB Output is correct
4 Correct 67 ms 74184 KB Output is correct
5 Correct 2 ms 3156 KB Output is correct
6 Correct 61 ms 73932 KB Output is correct

Subtask #2
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1748 KB Output is correct
2 Correct 869 ms 585104 KB Output is correct
3 Correct 790 ms 585744 KB Output is correct
4 Correct 775 ms 585932 KB Output is correct
5 Correct 785 ms 585816 KB Output is correct
6 Correct 816 ms 586000 KB Output is correct
7 Correct 771 ms 585792 KB Output is correct

Subtask #3
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1748 KB Output is correct
2 Correct 94 ms 75572 KB Output is correct
3 Correct 122 ms 75776 KB Output is correct
4 Correct 88 ms 75052 KB Output is correct
5 Correct 96 ms 74976 KB Output is correct
6 Correct 104 ms 75168 KB Output is correct
7 Correct 102 ms 75088 KB Output is correct
8 Correct 83 ms 74928 KB Output is correct
9 Correct 88 ms 74820 KB Output is correct
10 Correct 79 ms 74800 KB Output is correct
11 Correct 119 ms 75156 KB Output is correct
12 Correct 185 ms 75272 KB Output is correct
13 Correct 161 ms 75084 KB Output is correct

Subtask #4
0.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1748 KB Output is correct
2 Correct 94 ms 75572 KB Output is correct
3 Correct 122 ms 75776 KB Output is correct
4 Correct 88 ms 75052 KB Output is correct
5 Correct 96 ms 74976 KB Output is correct
6 Correct 104 ms 75168 KB Output is correct
7 Correct 102 ms 75088 KB Output is correct
8 Correct 83 ms 74928 KB Output is correct
9 Correct 88 ms 74820 KB Output is correct
10 Correct 79 ms 74800 KB Output is correct
11 Correct 119 ms 75156 KB Output is correct
12 Correct 185 ms 75272 KB Output is correct
13 Correct 161 ms 75084 KB Output is correct
14 Correct 2 ms 1748 KB Output is correct
15 Correct 200 ms 75344 KB Output is correct
16 Correct 102 ms 75548 KB Output is correct
17 Correct 83 ms 75016 KB Output is correct
18 Correct 86 ms 75132 KB Output is correct
19 Correct 110 ms 75164 KB Output is correct
20 Correct 109 ms 74932 KB Output is correct
21 Correct 93 ms 74956 KB Output is correct
22 Execution timed out 7071 ms 74960 KB Time limit exceeded
23 Halted 0 ms 0 KB -

Subtask #5
0.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1748 KB Output is correct
2 Correct 94 ms 75572 KB Output is correct
3 Correct 122 ms 75776 KB Output is correct
4 Correct 88 ms 75052 KB Output is correct
5 Correct 96 ms 74976 KB Output is correct
6 Correct 104 ms 75168 KB Output is correct
7 Correct 102 ms 75088 KB Output is correct
8 Correct 83 ms 74928 KB Output is correct
9 Correct 88 ms 74820 KB Output is correct
10 Correct 79 ms 74800 KB Output is correct
11 Correct 119 ms 75156 KB Output is correct
12 Correct 185 ms 75272 KB Output is correct
13 Correct 161 ms 75084 KB Output is correct
14 Correct 2 ms 1748 KB Output is correct
15 Correct 200 ms 75344 KB Output is correct
16 Correct 102 ms 75548 KB Output is correct
17 Correct 83 ms 75016 KB Output is correct
18 Correct 86 ms 75132 KB Output is correct
19 Correct 110 ms 75164 KB Output is correct
20 Correct 109 ms 74932 KB Output is correct
21 Correct 93 ms 74956 KB Output is correct
22 Execution timed out 7071 ms 74960 KB Time limit exceeded
23 Halted 0 ms 0 KB -

Subtask #6
0.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1748 KB Output is correct
2 Correct 869 ms 585104 KB Output is correct
3 Correct 790 ms 585744 KB Output is correct
4 Correct 775 ms 585932 KB Output is correct
5 Correct 785 ms 585816 KB Output is correct
6 Correct 816 ms 586000 KB Output is correct
7 Correct 771 ms 585792 KB Output is correct
8 Correct 2 ms 1748 KB Output is correct
9 Correct 94 ms 75572 KB Output is correct
10 Correct 122 ms 75776 KB Output is correct
11 Correct 88 ms 75052 KB Output is correct
12 Correct 96 ms 74976 KB Output is correct
13 Correct 104 ms 75168 KB Output is correct
14 Correct 102 ms 75088 KB Output is correct
15 Correct 83 ms 74928 KB Output is correct
16 Correct 88 ms 74820 KB Output is correct
17 Correct 79 ms 74800 KB Output is correct
18 Correct 119 ms 75156 KB Output is correct
19 Correct 185 ms 75272 KB Output is correct
20 Correct 161 ms 75084 KB Output is correct
21 Correct 2 ms 1748 KB Output is correct
22 Correct 200 ms 75344 KB Output is correct
23 Correct 102 ms 75548 KB Output is correct
24 Correct 83 ms 75016 KB Output is correct
25 Correct 86 ms 75132 KB Output is correct
26 Correct 110 ms 75164 KB Output is correct
27 Correct 109 ms 74932 KB Output is correct
28 Correct 93 ms 74956 KB Output is correct
29 Execution timed out 7071 ms 74960 KB Time limit exceeded
30 Halted 0 ms 0 KB -