Submission #825818

#	Time	Username	Problem	Language	Result	Execution time	Memory
825818		lollipop	Prisoner Challenge (IOI22_prison)	C++17	10 / 100	5 ms	596 KiB

prison

#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 "prison.h"

struct stu{
    int tp , xr , bg ;
};
stu app[ 70 ] ;
int pos[ 30 ][ 30 ] ;
vector<vector<int>> devise_strategy(int N){
     int xx[ 10 ] ;
     xx[ 0 ] = 1 ;
     for( int j = 1 ; j <= 7 ; j ++ ) xx[ j ] = xx[ j - 1 ] * 3 ;
     int cur = 1 , tt = 1 ;
     for( int j = 0 ; j <= 7 ; j ++ ){
        stu a ; a.tp = 0 ; a.xr = j ; a.bg = tt ;
        app[ cur ] = a ; a.tp = 1 ;
        app[ cur + 1 ] = a ; a.tp = 2 ;
        app[ cur + 2 ] = a ;
        pos[ 0 ][ j ] = cur ;
        pos[ 1 ][ j ] = cur + 1 ;
        pos[ 2 ][ j ] = cur + 2 ;
        tt = ( tt + 1 ) % 2 ;
        cur += 3 ;
     }
// 0 --> A , 1 --> B
     vector < int > v ;
     vector < vector < int > > ans ;
     
     v.pb( 0 ) ;
     int st = 7 ;
     for( int j = 1 ; j <= N ; j ++ ){
       // now get which type is this number for the st 
       int x = j ;
       int cc = 0 ;
       if( x >= xx[ st ] ){
          cc ++ ; 
          x -= xx[ st ] ;
       }
       if( x >= xx[ st ] ){
          cc ++ ; 
          x -= xx[ st ] ;
       }
       v.pb( pos[ cc ][ st ] ) ;     
     }
     ans.pb( v ) ;
     for( int j = 1 ; j < cur ; j ++ ){
        v.clear() ;
        stu axl = app[ j ] ;
        if( axl.bg == 1 ) v.pb( 1 ) ;
        else v.pb( 0 ) ;
        int ss = axl.xr ;
        int cc = axl.tp ;
        for( int nmb = 1 ; nmb <= N ; nmb ++ ){
            int x = nmb ; 
            for( int k = 7 ; k > ss ; k -- ){
               if( x >= xx[ k ] ) x -= xx[ k ] ;
               if( x >= xx[ k ] ) x -= xx[ k ] ; 
            }
            int cnt = 0;
            if( x >= xx[ ss ] ) cnt ++ , x-= xx[ ss ] ;
            if( x >= xx[ ss ] ) cnt ++ , x-= xx[ ss ] ;
            if( cnt < cc ){
               if( axl.bg == 1 ) v.pb( -2 ) ;
               else v.pb( -1 ) ;
               continue ;
            }
            if( cnt > cc ){
               if( axl.bg == 1 ) v.pb( -1 ) ;
               else v.pb( -2 ) ;
               continue ;               
            }
            int xixo = 0 ;
            if( x >= xx[ ss - 1 ] ) xixo ++ , x-= xx[ ss - 1 ] ;
            if( x >= xx[ ss - 1 ] ) xixo ++ , x-= xx[ ss - 1 ] ;
            v.pb( pos[ xixo ][ ss - 1 ] ) ;
        }
        ans.pb( v ) ; 
     }
     return ans ;
}




// static constexpr int kNumPrisoners = 500;

// static void invalid_strategy(std::string message) {
//   printf("%s\n", message.c_str());
//   exit(0);
// }

// int main() {
//   int N;
//   assert(1 == scanf("%d", &N));

//   std::vector<std::vector<int>> strategy = devise_strategy(N);
//   if (strategy.size() == 0) {
//     invalid_strategy("s is an empty array");
//   }
//   int x = strategy.size() - 1;
//   for (int i = 0; i <= x; ++i) {
//     if (static_cast<int>(strategy[i].size()) != N + 1) {
//       invalid_strategy("s[i] contains incorrect length");
//     }
//     if (strategy[i][0] < 0 || strategy[i][0] > 1) {
//       invalid_strategy("First element of s[i] is non-binary"); 
//     }
//     for (int j = 1; j <= N; ++j) {
//       if (strategy[i][j] < -2 || strategy[i][j] > x) {
//         invalid_strategy("s[i][j] contains incorrect value");
//       }
//     }
//   }

//   FILE *log_file = fopen("log.txt","w");

//   int A, B;
//   while (1 == scanf("%d", &A) && A != -1) {
//     assert(1 == scanf("%d", &B));
//     bool answer = false;
//     int whiteboard = 0;
//     for (int i = 0; i < kNumPrisoners && !answer; ++i) {
//       int check = strategy[whiteboard][0];
//       whiteboard = strategy[whiteboard][check == 0 ? A : B];
//       if (whiteboard < 0) {
//         answer = true;
//         printf("%c\n", "BA"[whiteboard + 2]);
//       } else {
//         if (i > 0) {
//           fprintf(log_file, " ");
//         }
//         fprintf(log_file, "%d", whiteboard);
//       }
//     }
//     if (!answer) {
//       printf("X\n");
//     }
//     fprintf(log_file, "\n");
//     fflush(log_file);
//   }
// }

• Subtask 1: 5 / 5
• Subtask 2: 5 / 5
• Subtask 3: 0 / 90