Submission #626428

#	Time	Username	Problem	Language	Result	Execution time	Memory
626428		mraron	죄수들의 도전 (IOI22_prison)	C++17	65 / 100	39 ms	1084 KiB

prison

#include "prison.h"

#include <vector>
#include <iostream>
#include <cassert>
#include <algorithm>
using namespace std;

int get_bit(int x, int bit, int base=2) {
    vector<int> lst;
    while(x>0) {
        lst.push_back(x%base);
        x/=base;
    }
    
    return (bit>=(int)lst.size()?0:lst[bit]);
}

std::vector<std::vector<int>> devise_strategy(int N) {
    //~ cerr<<get_bit(4, 0)<<"\n";
    //~ exit(0);
    const int BASE=2;
    const int START=12;
    int x=24;
    std::vector<std::vector<int>> s(x+1, std::vector<int>(N+1, 0));
    //~ cerr<<"digraph G {\n";
    for(int i=0;i<=x;++i) {
        if(i==0) {
            s[i][0]=0;
            for(int j=1;j<=N;++j) {
                s[i][j]=1+get_bit(j, START, BASE);
                //~ cerr<<i<<" -> "<<s[i][j]<<"\n";
            }
        }else {
            int bit=START-(i-1)/BASE;
            int bag=(bit&1)^1;
            
            int have=(i-1)%BASE;
            s[i][0]=bag;
            int THIS=bag==0?-1:-2;
            int OTHER=bag==0?-2:-1;
            for(int j=1;j<=N;++j) {
                int curr=get_bit(j,bit, BASE);
                if(curr>have) {
                    s[i][j]=OTHER;
                }else if(curr<have) {
                    s[i][j]=THIS;
                }else {
                    int nxt=get_bit(j, bit-1, BASE);
                    //~ std::cerr<<i<<" "<<j<<" "<<bit-1<<" "<<nxt<<"!!\n";
                    if(bit-1==0) {
                        if(nxt==0) {
                            s[i][j]=THIS;
                        }else {
                            s[i][j]=OTHER;
                        }
                    }else {
                        //~ std::cerr<<i<<" "<<2*(bit+1)+1+nxt<<"\n";
                        //~ assert(i!=2*(12-bit+1)+1+nxt);
                        s[i][j]=BASE*(START-bit+1)+1+nxt;
                        //~ cerr<<i<<" -> "<<s[i][j]<<"\n";
                    }
                }
            }
        }
    }
    //~ cerr<<"}\n";
    return s;
}
//~ 0 -> 1 2
//~ 1 -> 3 4
//~ 2 -> 5 6

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