Submission #887573

#	Time	Username	Problem	Language	Result	Execution time	Memory
887573		jay_jayjay	Lockpicking (IOI23_lockpicking)	C++17	100 / 100	1 ms	608 KiB

lockpicking

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

void define_states(int m, vector<int> b, vector<vector<int>> t, int j0);

// void define_states(int m, vector<int> b, vector<vector<int>> t ,int j0) {
        // printf("states: len = %d; initial = %d\n",m,j0);
        // printf("b sz = %d; t sz = %d\n",b.size(),t.size());
        // for(int i=0;i<m;i++) {
                // printf("%d: (%d)  (0 -> %d) (1 -> %d)\n",i,b[i],t[i][0],t[i][1]);
        // }
// }

// inp
int n;
vector<int> a;
vector<vector<int>> s;

// out
vector<int> b;
vector<vector<int>> t;

map<vector<int>,int> mp;

int vv=0;

void pv(vector<int> st) {
        printf("{");
        for(auto x:st)printf("%d ",x);
        printf("}");
}

void dfs(int& v, vector<int> st) {
        // printf("dfs st=");pv(st);printf("\n");
        if(st.size()==0) return void(v=0);
        int c=0;
        for(auto x:st) c+=2*a[x]-1;
        int z = c>=0;
        
        if(mp.find(st) != mp.end()) return void(v=mp[st]);
        v=vv++;
        mp[st]=v;
        vector<int> zz,oo;
        for(auto x:st) {
                if(a[x] == 0) zz.push_back(s[x][z]);
                if(a[x] == 1) oo.push_back(s[x][z]);
        }
        
        b.push_back(z);
        t.push_back({-69,-42});
        
        dfs(t[v][0], zz);
        dfs(t[v][1], oo);
        
        // printf("state v=%d, output %d: ",v,z);
        // pv(st);
        // printf(" (0 -> %d)",t[v][0]);
        // pv(zz);
        // printf(" (1 -> %d)",t[v][1]);
        // pv(oo);
        // printf("\n");
}

void construct_card(int n, vector<int> a, vector<vector<int>> s) {
        // n, a is output bit, s is transition
        ::n=n;::a=a;::s=s;
        
        vector<int> al;
        for(int i=0;i<n;i++)al.push_back(i);
        
        int rt=0;
        dfs(rt,al);
        
        define_states(vv, b, t, rt);
}

/*int main()
{
        int n;scanf("%d",&n);
        vector<int> x(n);
        vector<vector<int>> y(n,vector<int>(2));
        for(int i=0;i<n;i++) {
                scanf("%d%d%d",&x[i],&y[i][0],&y[i][1]);
        }
        
        construct_card(n,x,y);
}
*/

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