제출 #1241499

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1241499		sano	Prisoner Challenge (IOI22_prison)	C++20	65 / 100	7 ms	1236 KiB

prison

#include<iostream>
#include<vector>
#include<queue>
#include<deque>
#include<string>
#include<fstream>
#include<algorithm>
#include <iomanip>
#include<map>
#include <set>
#include <unordered_map>
#include <stack>
#include <unordered_set>
#include <cmath>
#include <cstdint>
#include <cassert>
#include <bitset>
#include <random>
#include <chrono>
#include <cstring>
#define shit short int
#define ll long long
#define ld long double
//#define int ll
#define For(i, n) for(int i = 0; i < (int)n; i++)
#define ffor(i, a, n) for(int i = (int)a; i < (int)n; i++)
#define rfor(i, n) for(int i = (int)n; i >= (int)0; i--)
#define rffor(i, a, n) for(int i = (int)n; i >= (int)a; i--)
#define vec vector
#define ff first
#define ss second
#define pb push_back
#define pii pair<long double, long double>
#define pld pair<ld, ld>
#define NEK 200000000000000
#define mod 1000000007
#define mod2 1000000009
#define rsz resize 
#define prv 43
#define prv2 47
#define D 8
#define trav(a,x) for (auto& a: x)
#define pb push_back
#define ub upper_bound
#define lb lower_bound
#define all(x) (x).begin(), (x).end()
#define sig 0.0000001

using namespace std;

int daj(int a, int ktore) {
    if (ktore < 0) return 0;
    while (ktore) {
        a /= 3;
        ktore--;
    }
    a %= 3;
    return a;
}

int umocni(int a, int b) {
    int vys = 1;
    while (b) {
        if ((b % 2) == 1) {
            vys *= a;
        }
        a *= a;
        b /= 2;
    }
    return vys;
}

vec<vec<int>> devise_strategy(int n) {
    int log = 0;
    while (umocni(3, log) <= n) log++;
    int x = log + log * 2;
    vec<vec<int>> s(x + 1, vec<int>(n + 1));
    s[0][0] = 0;
    int hod0 = 1 - ((log - 1) % 2);
    for (int i = 1; i <= n; i++) {
        s[0][i] = (log-1) + log * (daj(i, log - 1)) + 1;
    }
    ffor(i, 1, x + 1) {
        int mi = i - 1;
        if (((mi % log) % 2) == hod0) {
            s[i][0] = 0;
        }
        else {
            s[i][0] = 1;
        }
        for (int j = 1; j <= n; j++) {
            int ktore = mi % log;
            int hod = mi / log;
            int jeho_hod = daj(j, ktore);
            if (jeho_hod > hod) {
                if (s[i][0] == 0) {
                    s[i][j] = -2;
                }
                else {
                    s[i][j] = -1;
                }
            }
            if (jeho_hod < hod) {
                if (s[i][0] == 0) {
                    s[i][j] = -1;
                }
                else {
                    s[i][j] = -2;
                }
            }
            if (jeho_hod == hod) {
                ktore--;
                hod = daj(j, ktore);
                s[i][j] = ktore + log * hod + 1;
            }
        }
    }
    return s;
    /*
    int x = 32;
    vec<vec<int>> s(x + 1, vec<int>(n+1));
    s[0][0] = 0;
    for (int j = 1; j < n; j++) {
        s[0][j] = 8 * daj(j, 0) + 1;
    }
    ffor(i, 1, x + 1) {
        s[i][0] = 1 - (i % 2);
        for (int j = 1; j < n; j++) {
            //na tabuly je napisane i, ja som v krabici videl j
            int ktore = (i-1) % 8;
            int kolko = ((i-1) / 8) % 8;
            int hod = daj(j, ktore);
            if (hod == kolko) {
                s[i][j] = (ktore + 1) + 8 * daj(j, ktore + 1) + 1;
            }
            else {
                if (hod > kolko) {
                    s[i][j] = (-1) * (1 + s[i][0]) + 1;
                }
                if (hod < kolko) {
                    s[i][j] = (-1) * (2 - s[i][0]) + 1;
                }
            }
        }
    }
    return s;*/
}

int krokuj(vec<vec<int>>& s, int x, int a, int b) {
    //cout << x << endl;
    if (x < 0) {
        return x;
    }
    int k;
    if (s[x][0] == 0) {
        //cout << 'A' << endl;
        k = a;
    }
    else {
        //cout << 'B' << endl;
        k = b;
    }
    return krokuj(s, s[x][k], a, b);
}
/*signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    //cin >> n;
    while (1) {
        int n;
        //n = rand() % 500 + 2;
        cin >> n;
        int a = 0, b = 0;
        cin >> a >> b;
        //while (a == b) {
        //    a = rand() % n + 1;
        //    b = rand() % n + 1;
       // }
        vec<vec<int>> s = devise_strategy(n);
        int odp = krokuj(s, 0, a, b);
        cout << odp << '\n';
        if (odp == -1 && (a > b)) {
            int lol = 1;
            cout << n << ' ' << a << ' ' << b << endl;
            return 0;
        }
        if (odp == -2 && (b > a)) {
            int lol = 1;
            cout << n << ' ' << a << ' ' << b << endl;
            return 0;
        }
    }
    return 0;
}*/

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