제출 #634775

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
634775		Ozy	죄수들의 도전 (IOI22_prison)	C++17	65 / 100	12 ms	1616 KiB

prison

#include "prison.h"
#include <bits/stdc++.h>
using namespace std;
#define lli long long int
#define debug(a) cout << #a << " = " << a << endl
#define debugsl(a) cout << #a << " = " << a << ", "
#define rep(i,a,b) for (int i = (a); i <= (b); i++)
#define repa(i,a,b) for (int i = (a); i >= (b); i--)

vector<vector<int> > strat;
int tam,a,num,ant,yo,otro,imp,par;

std::vector<std::vector<int>> devise_strategy(int N) {

    //cambiar para futuras soluciones
    tam = 25;

    strat.resize(tam);
    rep(i,0,tam-1) strat[i].resize(N+1);

    //definir la bolsa en la que van a buscar
    strat[0][0] = 0;
    a = 1;
    for(int i = 1; i < 24; i+=2) {
        strat[i][0] = a;
        strat[i+1][0] = a;
        a ^= 1;
    }

    lli pot = 12;
    yo = -1;
    otro = -2;

    //empezado por el cero
    num = (1<<pot);
    rep(i,1,N) {
        if (i&num) strat[0][i] = 1;
        else strat[0][i] = 2;
    }

    //llenar la tabla de manera normal
    rep(i,1,22) {
        if (i&1) {
            pot--;
            swap(yo,otro);
            imp = i+2;
            par = i+3;
        }
        num = 1<<pot;
        ant = num*2;

        rep(j,1,N) {
            if ((j&ant) && (i%2) == 0) {strat[i][j] = otro; continue;}
            if (!(j&ant) && (i%2) == 1) {strat[i][j] = yo;  continue;}

            a = num&j;
            if (a) strat[i][j] = imp;
            else strat[i][j] = par;
        }

    }

    //chcear lo de el caso especial, ultimo bit forzoso es diferente
    pot--;
    swap(otro,yo);

    rep(i,23,24) {
        num = 1<<pot;
        ant = num*2;
        rep(j,1,N) {
            if ((j&ant) && (i%2) == 0) {strat[i][j] = otro; continue;}
            if (!(j&ant) && (i%2) == 1) {strat[i][j] = yo;  continue;}

            a = num&j;
            if (a) strat[i][j] = otro;
            else strat[i][j] = yo;
        }
    }

    //rep(i,1,N) {
    //    rep(j,21,24) debugsl(strat[j][i]);
    //    cout << endl;
    //}

    return strat;
}

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