제출 #629115

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
629115		daria	죄수들의 도전 (IOI22_prison)	C++17	72 / 100	17 ms	1108 KiB

prison

#include "bits/stdc++.h"
#include "prison.h"
using namespace std;
#define ll int

vector<vector<int> > devise_strategy(int N) {
 vector<vector<int> > s(24, vector<int>(N+1, 0));
 int v[6][4], mp[24], c = 1;
 for(int i=0; i<6; ++i){
  for(int j=0; j<4; ++j){
   if(i == 0 && j == 3){
    v[i][j] = 0;
   } else{
    mp[c] = j;
    v[i][j] = c++;
   }
  }
 }
 int ans[2] = {-1, -2};
 s[0][0] = 1;
 for(int j=1; j<=N; ++j){
  int bit = (j >> 11)%4;
  s[0][j] = v[0][bit];
 }
 for(int i=1; i<24; ++i){
  int k = i/4;
  s[i][0] = k%2;
  for(int j=1; j<=N; ++j){
   int pow = (1 << (11-2*k));
   int bit = (j/pow)%4;
   if(bit > mp[i]) s[i][j] = ans[1-k%2];
   if(bit < mp[i]) s[i][j] = ans[k%2];
   if(bit == mp[i]){
    if(k<5) s[i][j] = v[k+1][(j >> (9-2*k))%4];
    int l = 0, r = -1;
    for(int h = 11-2*k; h <= 11; h+=2){
     if(j%(1 << h) <= l) s[i][j] = ans[k%2];
     if(j%(1 << h) >= (1 << h)+r) s[i][j] = ans[1-k%2];
     l++; r--;
    }
   }
   if(j <= k+1) s[i][j] = ans[k%2];
   if(j >= N-k) s[i][j] = ans[1-k%2];
  // cout << s[i][j] << " ";
  } //cout << endl;
 }
 return s;
}

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