Submission #626144

#	Time	Username	Problem	Language	Result	Execution time	Memory
626144		peti1234	Prisoner Challenge (IOI22_prison)	C++17	100 / 100	10 ms	1236 KiB

prison

#include <bits/stdc++.h>

using namespace std;

vector<vector<int> > devise_strategy(int n){
    vector<vector<int>> ans(21), ert(9), spec(9);
    vector<int> szint(21, 0);
    for (int i=0; i<=20; i++) {
        ans[i].resize(n+1);
        if (i<=8) ert[i].resize(n+1), spec[i].resize(n+1);
    }
    for (int i=0; i<=19; i++) {
        szint[i]=(i+2)/3;
    }
    szint[20]=8;

    for (int i=0; i<=20; i++) {
        ans[i][0]=(szint[i]%2);
    }

    for (int j=1; j<=n; j++) {
        int kis=1, nagy=5102;
        for (int i=0; i<=8; i++) {
            int res=0, res2=0;
            if (j==26) {
                //cout << "lepes " << kis << " " << nagy << "\n";
            }
            if (j==kis) res2=-1, res=1;
            if (j==nagy) res2=-2, res=3;
            if (kis<j && j<nagy) {
                kis++, nagy--;
                if (i<6) {
                    int k1=kis+(nagy+1-kis)/3, k2=2*k1-kis;
                    if (j<k1) res=1, nagy=k1-1;
                    else if (j<k2) res=2, kis=k1, nagy=k2-1;
                    else res=3, kis=k2;
                }
                if (i==6) res=19;
                if (i==7) res=20;
                if (i==8) res=0;
            }
            ert[i][j]=res, spec[i][j]=res2;
            if (j==7 || j==8) {
                //cout << "vege " << res << " " << res2 << "\n";
            }
        }
    }
    //cout << "vege " << ert[4][26] << "\n";
    for (int i=0; i<=20; i++) {
        for (int j=1; j<=n; j++) {
            int ut=(1<=i && i<=18 ? (i-1)%3+1 : 0), b=ert[szint[i]][j], sp=spec[szint[i]][j], el=(1<=i && i<=18 ? ert[szint[i]-1][j] : 0);
            if (ut!=el || sp) {
                if (ut!=el) ans[i][j]=(el<ut ? -1 : -2);
                else ans[i][j]=sp;
                if (szint[i]%2) ans[i][j]=-3-ans[i][j];
                /*if (i==13 && j==26) {
                    cout << "rossz " << b << " " << szint[i] << " " << ans[i][j] << "\n";
                    cout << ut << " " << b << " " << sp << "\n";
                }*/
            } else {
                ans[i][j]=(i<16 ? i+(3-i%3)%3+b : b);
            }
        }
    }
    return ans;
}
void solve(vector<vector<int> > &sz, int a, int b) {
    int pos=0, ans=0, lep=0;
    while (lep<20 && ans==0) {
        int kerd=(sz[pos][0]%2 ? b : a), kov=sz[pos][kerd];
        //cout << "fontos " << pos << " " << kerd << " " << kov << "\n";
        if (kov<0) {
            ans=kov;
        } else {
            pos=kov, lep++;
        }
    }
    if (lep>=20) {
        cout << "vegtelen " << a << " " << b << "\n";
        exit(0);
    }
    if (ans==-1 && a>b || ans==-2 && a<b) {
        cout << "rossz valasz " << a << " " << b << "\n";
        exit(0);
    }
}
/*
int main()
{
    int n=5000;
    //cin >> n;
    vector<vector<int> > sz=devise_strategy(n);
    for (int i=1; i<=n; i++) {
        for (int j=1; j<=n; j++) {
            if (i!=j) {
                solve(sz, i, j);
            }
        }
    }
    //solve(sz, 8, 7);
    for (auto x:sz) {
        cout << "sor " << cnt << ": ";
        if (cnt<10) cout << " ";
        cnt++;
        for (auto y:x) {
            if (0<=y && y<10) cout << " ";
            cout << y << " ";
        }
        cout << "\n";
    }
    return 0;
}
*/

Compilation message (stderr)

prison.cpp: In function 'void solve(std::vector<std::vector<int> >&, int, int)':
prison.cpp:82:17: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
   82 |     if (ans==-1 && a>b || ans==-2 && a<b) {
      |         ~~~~~~~~^~~~~~

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