Submission #1155324

#	Time	Username	Problem	Language	Result	Execution time	Memory
1155324		firewater	Lockpicking (IOI23_lockpicking)	C++20	100 / 100	15 ms	6396 KiB

lockpicking

#include <vector>
#include<bits/stdc++.h>
#define ll long long
using namespace std;

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

vector<int>two;
vector<int>B;
vector<vector<int> >T;
int n,m,ini,now,sav,x,y;
vector<int>st[50500];
int np()
{
    B.push_back(0);
    T.push_back(two);
    return (m++);
}
void construct_card(int N, std::vector<int> A, std::vector<std::vector<int>> S) {
    n=N;
    m=0;
    B.clear();
    T.clear();
    
    two.clear();
    two.push_back(0);
    two.push_back(0);
    
    //copy
    for(int i=0;i<n;++i){
        np();
        B[i]=A[i];
        T[i]=S[i];
    }
    
    ini=now=np();
    for(int i=0;i<n;++i)st[now].push_back(i);//initial set
    //begin
    while(now<m){
        
        if(st[now].size()==0){
            now++;
            continue;
        }
        
        sav=A[st[now][0]];
        B[now]=sav;
        if(st[now].size()==1||now>23000){
            T[now][sav]=S[st[now][0]][sav];
            now++;
            continue;
        }

        
        if(m<40000)x=np();//sav
		else x=S[st[now][0]][sav];
        if(m<40000)y=np();//sav^1
		else y=S[st[now][0]][sav^1];
        T[now][sav]=x;
        T[now][sav^1]=y;

        
        for(int i=0;i<st[now].size();++i){
            if(A[st[now][i]]==sav){
                st[x].push_back(S[st[now][i]][sav]);
            }
            else{
                st[y].push_back(S[st[now][i]][sav]);
            }
        }
        now++;
    }

    define_states(m,B,T,ini);
	return;
}

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