제출 #1271797

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1271797		Aviansh	죄수들의 도전 (IOI22_prison)	C++20	80 / 100	11 ms	1092 KiB

prison

#include "prison.h"
#include <bits/stdc++.h>

using namespace std;

map<array<int,2>,int>mp;
map<int,array<int,2>>rev;
int x = 22;

void pre(){
    int cn = 1;
    mp[{8,0}]=0;
    rev[0]={8,0};
    for(int i = 0;i<8;i++){
        mp[{i,1}]=cn;
        rev[cn++]={i,1};
        if(i==0){
            continue;
        }
        mp[{i,0}]=cn;
        rev[cn++]={i,0};
        mp[{i,2}]=cn;
        rev[cn++]={i,2};
    }
}

string base3(int n){
    string s = "";
    while(n){
        s+=to_string(n%3);
        n/=3;
    }
    while(s.size()<8){
        s+="0";
    }
    return s;
}

int ret(array<int,2>a, int val){
    if(val==0){
        if(a[0]%2){
            return 0;
        }
        return 1;
    }
    string vals = base3(val);
    int v = vals[a[0]]-'0';

    if(v>a[1]&&a[0]!=8){
        //this one is greater
        if(a[0]%2){
            return -2;
        }
        else{
            return -1;
        }
    }
    else if(v<a[1]&&a[0]!=8){
        if(a[0]%2){
            return -1;
        }
        else{
            return -2;
        }
    }
    else{
        //equal
        if(a[0]==1){
            if(vals[a[0]-1]-'0'==2){
                return -2;
            }
            if(vals[a[0]-1]-'0'==0){
                return -1;
            }
        }
        return mp[{a[0]-1,vals[a[0]-1]-'0'}];
    }
}



vector<vector<int>> devise_strategy(int n) {
    pre();
    vector<vector<int>>s(x+1, vector<int>(n+1));
    for(int i = 0;i<=x;i++){
        for(int j = 0;j<=n;j++){
            s[i][j]=ret(rev[i],j);
        }
    }
    return s;
}

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