제출 #978108

#제출 시각아이디문제언어결과실행 시간메모리
978108mircea_007죄수들의 도전 (IOI22_prison)C++17
65 / 100
10 ms1116 KiB
#include "prison.h" #include <vector> #include <stdio.h> // solutie x = 24 /* strategie proasta: baza B, K cifre citesti cifra din A, scrii in stare compari: diferit => return egal => MAI TREBUIE O STARE DE REDIRECTIONARE cum repari: pentru deja stii valoarea lui B atunci scrii starea in functie de B */ namespace Solver { const int BASE = 3; const int DIGITS = 8; std::vector<int> pb; std::vector<int> getpb() { std::vector<int> ret( 1, 1 ); while( (int)ret.size() <= DIGITS ) ret.push_back( ret.back() * BASE ); return ret; } int extract( int num, int idx ) { if( idx >= DIGITS ) return -1; return (num / pb[DIGITS - idx - 1]) % BASE; } int beats( int win, int lose ) { if( win == 0 ) return -2; return -1; } std::vector<std::vector<int>> devise_strategy( int N ) { pb = getpb(); // cum fac asta cu constexpr? // ret[y < x][0] = action std::vector<std::vector<int>> ret(1 + BASE * DIGITS, std::vector<int>(N + 1, 0)); // x = 24 // starea initiala => citim 1 ret[0][0] = 1; for( int val = 1 ; val <= N ; val++ ) ret[0][val] = 1 + extract( val, 0 ); for( int idx = 0 ; idx < DIGITS ; idx++ ){ bool t = (idx & 1); for( int dig = 0 ; dig < BASE ; dig++ ){ int state = 1 + idx * BASE + dig; ret[state][0] = t; for( int valt = 1 ; valt <= N ; valt++ ){ int digt = extract( valt, idx ); if( digt < dig ) ret[state][valt] = beats( !t, t ); else if( digt > dig ) ret[state][valt] = beats( t, !t ); else ret[state][valt] = 1 + BASE * (idx+1) + extract( valt, idx+1 ); // cifra idx+1 a lui t } } } // scoate starile pe care nu le atingem for( auto &lin : ret ) for( auto &el : lin ) if( el >= (int)ret.size() ) el = -1; return ret; } } std::vector<std::vector<int>> devise_strategy( int N ) { return Solver::devise_strategy( N ); }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...