제출 #1029112

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

prison

#include <bits/stdc++.h>
#include "prison.h"
using namespace std;
typedef long long ll;

// 1 2 3       4 5 6      7 8 9         10 11 12     13 14 15     16 17       18 19         20
//poziom 1    poziom 2    poziom 3      poziom 4     poziom 5     poziom 6    poziom 7    poziom 8

int poz[21];

vector<vector<int>> s(21);
vector<int> na_poziomie[10];
//vector<pair<int,int>> przedzialy[10];

void obl(int gl, int a, int b, int jak){
    if(a > b) return;

    int x, y;
    if(gl % 2 == 0){
        x = -1;
        y = -2;
    }
    else{
        x = -2;
        y = -1;
    }

    //przedzialy[gl].push_back({a,b});
    if(gl < 5){
        int kt = na_poziomie[gl][jak - 1];
        //cout << a << " " << b << " " << gl << "\N";
        s[kt][b] = y;
        s[kt][a] = x;


        for(int i = na_poziomie[gl+1][0]; i <= 20; ++i){
            if(poz[i] % 2 == 0){
                s[i][a] = -1;
                s[i][b] = -2;
            }
            else{
                s[i][a] = -2;
                s[i][b] = -1;
            }
        }

        a++;
        b--;
        if(a > b) return;
        int c = a + (b - a) / 3;
        int d = b - (b - a) / 3;
        if((b - a + 1) % 3 == 0){
            d--;
        }
        if(a <= c){
            for(int i = a; i <= c; ++i){
                s[kt][i] = na_poziomie[gl + 1][0];
            }
            for(int i = gl + 1; i <= gl + 1; ++i){
                int gdz = na_poziomie[gl + 1][0];
                if(gdz == 0 or gdz > 20) continue;
                for(int j = c + 1; j <= b; ++j){
                    s[gdz][j] = (i % 2 == 1 ? -1 : -2);
                }
            }

            obl(gl + 1, a, c, 1);
        }
        if(c+1 <= d){
            for(int i = c + 1; i <= d; ++i){
                s[kt][i] = na_poziomie[gl + 1][1];
            }

            for(int i = gl + 1; i <= gl + 1; ++i){
                int gdz = na_poziomie[gl + 1][1];
                if(gdz == 0 or gdz > 20) continue;
                for(int j = a; j <= c; ++j){
                    s[gdz][j] = ((i % 2 == 1) ? -2 : -1);
                }
                for(int j = d + 1; j <= b; ++j){
                    s[gdz][j] = (i % 2 == 1 ? -1 : -2);
                }
            }

            obl(gl + 1, c + 1, d, 2);
        }
        if(d+1 <= b){
            for(int i = d + 1; i <= b; ++i){
                s[kt][i] = na_poziomie[gl + 1][2];
            }

            for(int i = gl + 1; i <= gl + 1; ++i){
                int gdz = na_poziomie[gl + 1][2];
                if(gdz == 0 or gdz > 20) continue;
                for(int j = a; j <= d; ++j){
                    s[gdz][j] = ((i % 2 == 1) ? -2 : -1);
                }
            }


            obl(gl + 1, d + 1, b, 3);
        }
    }
    else{
        int kt = na_poziomie[gl][jak - 1];
        //cout << a << " " << b << " " << gl << " " << kt << "\N";
        s[kt][b] = y;
        s[kt][a] = x;

        for(int i = na_poziomie[gl+1][0]; i <= 20; ++i){
            //cout << i << " debug\N";
            if(poz[i] % 2 == 0){
                s[i][a] = -1;
                s[i][b] = -2;
            }
            else{
                s[i][a] = -2;
                s[i][b] = -1;
            }
        }

        a++;
        b--;
        if(a > b) return;

        int c = a + (b - a) / 2;
        if(b - a + 1 <= 2){
            c = b;
        }
        //cout << a << " " << c << " " << b << "\N";
        if(a <= c){
            //cout << "%\N";
            for(int i = a; i <= c; ++i){
                s[kt][i] = na_poziomie[gl + 1][0];
            }

            for(int i = gl + 1; i <= gl + 1; ++i){
                int gdz = na_poziomie[gl + 1][0];
                if(gdz == 0 or gdz > 20) continue;
                for(int j = c + 1; j <= b; ++j){
                    s[gdz][j] = (i % 2 == 1 ? -1 : -2);
                }
            }


            obl(gl + 1, a, c, 1);
        }
        if(c + 1 <= b){
            //cout << "^\N";
            for(int i = c + 1; i <= b; ++i){
                s[kt][i] = na_poziomie[gl + 1][1];
            }

            for(int i = gl + 1; i <= gl + 1; ++i){
                int gdz = na_poziomie[gl + 1][1];
                if(gdz == 0 or gdz > 20) continue;
                for(int j = a; j <= c; ++j){
                    s[gdz][j] = (i % 2 == 1 ? -2 : -1);
                }
            }

            obl(gl + 1, c + 1, b, 2);
        }
    }   
    return;
}

vector<vector<int>> devise_strategy(int N){
    poz[0] = 0; poz[1] = poz[2] = poz[3] = 1; poz[4] = poz[5] = poz[6] = 2; poz[7] = poz[8] = poz[9] = 3; 
    poz[10] = poz[11] = poz[12] = 4; poz[13] = poz[14] = poz[15] = 5; poz[16] = poz[17] = 6; poz[18] = poz[19] = 7; poz[20] = 8; 
    for(int i = 0; i <= 20; ++i){
        na_poziomie[poz[i]].push_back(i);
    }
    for(int i = 0; i <= 20; ++i){
        s[i].resize(N + 1);
        int poziom = poz[i];
        s[i][0] = poziom % 2;
        for(int j = 1; j <= N; ++j){
            s[i][j] = 0;
        }
    }
    for(int i = 0; i <= 9; ++i){
        for(int j = 0; j < 2; ++j){
            na_poziomie[i].push_back(50);
        }
    }
    obl(0, 1, N, 1);
    // for(int i = 0; i <= 10; ++i){
    //     for(int j = 0; j <= N; ++j){
    //         cout << s[i][j] << " ";
    //     }
    //     cout << "\n";
    // }
    // cout << "\n";
    return s;
}

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