제출 #1076383

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

prison

#include "prison.h"
#include <bits/stdc++.h>

using namespace std;

using vi = vector<int>;

vector<vi> multiply(vector<vi> S0, int fact) {
    int x0 = S0.size(), n0 = int(S0[0].size()) - 1;
    int n = n0 * fact + 2;
    vector<vi> S(x0 + fact, vi(n + 1, 0));

    for(auto &sir : S0) {
        sir[0] ^= 1;
        for(auto &it : sir) 
            if(it < 0) it = -3 - it;
    }

    S[0][0] = 0;
    S[0][1] = -1; S[0][n] = -2;
    for(int i = 2; i <= n - 1; ++i)
        S[0][i] = (i - 2) / n0 + 1;

    ///copii de S0[0]
    for(int i = 1; i <= fact; ++i) {
        S[i][0] = S0[0][0];

        ///marginile
        for(int j = 1; j <= (i - 1) * n0 + 1; ++j)
            S[i][j] = -2;
        for(int j = i * n0 + 2; j <= n; ++j)
            S[i][j] = -1;

        ///mijlocul, copiat
        for(int j = 1; j <= n0; ++j) {
            int p = (i - 1) * n0 + j + 1;
            if(S0[0][j] < 0) S[i][p] = S0[0][j];
            else S[i][p] = S0[0][j] + fact;
        }
    }
    for(int i = fact + 1; i < x0 + fact; ++i) {
        S[i][0] = S0[i - fact][0];
        for(int j = 2; j <= n; ++j) {
            int v = S0[i - fact][(j - 2) % n0 + 1]; /// efectiv doar copiezi
            if(v < 0) S[i][j] = v;
            else S[i][j] = v + fact;
        }
    }

    return S;
}

vector<vi> devise_strategy(int N) {
    vi V = {1, 2, 2, 3, 3, 3, 3, 3};
    vector<vi> S = {{0, -1, -2}};
    for(auto it : V) S = multiply(S, it);
    int x = S.size();
//    cerr << "nmax = " <<  (int)S[0].size() << "\n";
//    printf("   x = %d\nN=%d\n", x, (int)S[0].size());
//    for(int v = 0; v < x; ++v) {
//        printf("%d: ", v);
//        for(auto it : S[v]) printf("%d ", it);
//        printf("\n");
//    }
    for(int i = 0; i < x; ++i)
        S[i].resize(N + 1);
    return S;
}

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