Submission #1155771

#	Time	Username	Problem	Language	Result	Execution time	Memory
1155771		onbert	Lockpicking (IOI23_lockpicking)	C++20	100 / 100	18 ms	4316 KiB

lockpicking

#include <bits/stdc++.h>
using namespace std;

void construct_card(int N, vector<int> A, vector<vector<int>> S);
void define_states(int M, vector<int> B, vector<vector<int>> T, int j0);

void construct_card(int n, vector<int> A, vector<vector<int>> S) {
	int m = n * n;
    vector<int> B(m);
    vector<vector<int>> T(m, vector<int>(2, -1));
    for (int i=0;i<m;i++) B[i] = A[i%n], T[i][B[i]] = S[i%n][B[i]] + i/n*n;
    for (int i=1;i<n;i++) {
        int u1 = i, u2 = 0;
        for (int j=0;j<n*n;j++) {
            int v1 = S[u1][B[u2]], v2 = T[u2][A[u1]];
            if (v2 == -1) {
                T[u2][A[u1]] = v1 + i * n;
                break;
            }
            u1 = v1, u2 = v2;
        }
    }
    for (int i=0;i<m;i++) for (int j=0;j<=1;j++) T[i][j] = max((int)0, T[i][j]);
    define_states(m, B, T, 0);
}

• Subtask 1: 21 / 21
• Subtask 2: 30 / 30
• Subtask 3: 20 / 20
• Subtask 4: 29 / 29