Submission #1029079

#	Time	Username	Problem	Language	Result	Execution time	Memory
1029079		jakubmz2	Prisoner Challenge (IOI22_prison)	C++17	0 / 100	1 ms	432 KiB

prison

#include <bits/stdc++.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] = -3;
        }
    }
    for(int i = 0; i <= 9; ++i){
        for(int j = 0; j < 2; ++j){
            na_poziomie[i].push_back(50);
        }
    }
    obl(0, 1, 5000, 1);
    // for(int i = 0; i <= 20; ++i){
    //     cout << "i: " << (i <= 9 ? "0" : "") << i << " ";
    //     for(int j = 0; j <= n; ++j){
    //         cout << (s[i][j] >= 0 ? "+" : "") << s[i][j] << " ";
    //     }
    //     cout << "\n";
    // }
    // cout << "\n";
    return s;
}

// bool spr(int a, int b){
//     int gdz = 0;
//     int d = 0;
//     //cout << a << " " << b << "\n";
//     for(int i = 0; i < 500; ++i){
//         int kt = s[gdz][0];
//         //cout << gdz << " " << kt << " gdzkt\n";
//         int val;
//         if(kt == 0){
//             val = a;
//         }
//         else{
//             val = b;
//         }
//         //cout << val << " val\n";
//         //cout << s[gdz][val] << " nxt\n";
//         if(s[gdz][val] == -1){
//             if(a < b){
//                 d = 2;
//                 break;
//             }
//             else{
//                 d = 1;
//                 cout << a << " " << b << " " << "ZLA ODP" << "\n";
//                 break;
//             }
//         }
//         else if(s[gdz][val] == -2){
//             if(a > b){
//                 d = 2;
//                 break;
//             }
//             else{
//                 d = 1;
//                 cout << a << " " << b << " " << "ZLA ODP" << "\n";
//                 break;
//             }
//         }
//         else if(s[gdz][val] == -3){
//             cout << a << " " << b << " " << "PROSZE NIE" << "\n";
//             d = 1;
//             break;
//         }
//         else{
//             gdz = s[gdz][val];
//         }
//     }  
//     if(d == 0){
//         cout << a << " " << b << " " << "BRAK" << "\n";
//         return false;
//     }
//     else if(d == 1){
//         return false;
//     }
//     else{
//         return true;
//     }
//     return false;
// }

// int main(){
//     int x = 5000;
//     devise_strategy(x);
//     // for(int i = 0; i <= 5; ++i){
//     //     cout << przedzialy[i][0].first << " " << przedzialy[i][0].second << "\n";
//     // }
//     // cout << "\n";

//     // for(int i = 1; i <= x; ++i){
//     //     for(int j = 1; j <= x; ++j){
//     //         if(i == j) continue;
//     //         if(spr(i, j) == false){
//     //             cout << i << " " << j << " ZLE\n";
//     //             return 0;
//     //         }
//     //     }
//     // }
//     return 0;
// }

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