oj.uz

Submission #887573

# Submission time Handle Problem Language Result Execution time Memory
887573 2023-12-14T18:40:29 Z jay_jayjay Lockpicking (IOI23_lockpicking) C++17
100 / 100
 1 ms 608 KB 
#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.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB ok, most errors: 1 (allowed: 1)
2 Correct 1 ms 348 KB ok, most errors: 0 (allowed: 1)
3 Correct 0 ms 348 KB ok, most errors: 0 (allowed: 1)
4 Correct 1 ms 432 KB ok, most errors: 1 (allowed: 1)
5 Correct 1 ms 348 KB ok, most errors: 1 (allowed: 1)
6 Correct 0 ms 352 KB ok, most errors: 1 (allowed: 1)
7 Correct 0 ms 344 KB ok, most errors: 1 (allowed: 1)
8 Correct 0 ms 348 KB ok, most errors: 1 (allowed: 1)
9 Correct 1 ms 348 KB ok, most errors: 1 (allowed: 1)
10 Correct 1 ms 348 KB ok, most errors: 1 (allowed: 1)
11 Correct 0 ms 348 KB ok, most errors: 1 (allowed: 1)
12 Correct 0 ms 352 KB ok, most errors: 1 (allowed: 1)

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 356 KB ok, most errors: 2 (allowed: 29)
2 Correct 1 ms 360 KB ok, most errors: 3 (allowed: 29)
3 Correct 1 ms 348 KB ok, most errors: 3 (allowed: 29)
4 Correct 1 ms 448 KB ok, most errors: 3 (allowed: 29)
5 Correct 0 ms 352 KB ok, most errors: 4 (allowed: 29)
6 Correct 0 ms 352 KB ok, most errors: 3 (allowed: 29)
7 Correct 0 ms 352 KB ok, most errors: 4 (allowed: 29)
8 Correct 0 ms 436 KB ok, most errors: 4 (allowed: 29)

Subtask #3
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 608 KB ok, most errors: 3 (allowed: 899)
2 Correct 0 ms 344 KB ok, most errors: 2 (allowed: 899)
3 Correct 0 ms 348 KB ok, most errors: 3 (allowed: 899)
4 Correct 0 ms 348 KB ok, most errors: 4 (allowed: 899)
5 Correct 1 ms 348 KB ok, most errors: 4 (allowed: 899)
6 Correct 0 ms 348 KB ok, most errors: 4 (allowed: 899)
7 Correct 0 ms 348 KB ok, most errors: 3 (allowed: 899)
8 Correct 1 ms 344 KB ok, most errors: 4 (allowed: 899)

Subtask #4
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB ok, most errors: 1 (allowed: 1)
2 Correct 1 ms 348 KB ok, most errors: 0 (allowed: 1)
3 Correct 0 ms 348 KB ok, most errors: 0 (allowed: 1)
4 Correct 1 ms 432 KB ok, most errors: 1 (allowed: 1)
5 Correct 1 ms 348 KB ok, most errors: 1 (allowed: 1)
6 Correct 0 ms 352 KB ok, most errors: 1 (allowed: 1)
7 Correct 0 ms 344 KB ok, most errors: 1 (allowed: 1)
8 Correct 0 ms 348 KB ok, most errors: 1 (allowed: 1)
9 Correct 1 ms 348 KB ok, most errors: 1 (allowed: 1)
10 Correct 1 ms 348 KB ok, most errors: 1 (allowed: 1)
11 Correct 0 ms 348 KB ok, most errors: 1 (allowed: 1)
12 Correct 0 ms 352 KB ok, most errors: 1 (allowed: 1)
13 Correct 1 ms 356 KB ok, most errors: 2 (allowed: 29)
14 Correct 1 ms 360 KB ok, most errors: 3 (allowed: 29)
15 Correct 1 ms 348 KB ok, most errors: 3 (allowed: 29)
16 Correct 1 ms 448 KB ok, most errors: 3 (allowed: 29)
17 Correct 0 ms 352 KB ok, most errors: 4 (allowed: 29)
18 Correct 0 ms 352 KB ok, most errors: 3 (allowed: 29)
19 Correct 0 ms 352 KB ok, most errors: 4 (allowed: 29)
20 Correct 0 ms 436 KB ok, most errors: 4 (allowed: 29)
21 Correct 1 ms 344 KB ok, most errors: 5 (allowed: 127)
22 Correct 1 ms 344 KB ok, most errors: 4 (allowed: 149)
23 Correct 1 ms 356 KB ok, most errors: 4 (allowed: 149)
24 Correct 1 ms 356 KB ok, most errors: 4 (allowed: 149)
25 Correct 1 ms 436 KB ok, most errors: 5 (allowed: 149)
26 Correct 1 ms 348 KB ok, most errors: 6 (allowed: 149)
27 Correct 1 ms 348 KB ok, most errors: 5 (allowed: 149)
28 Correct 1 ms 348 KB ok, most errors: 6 (allowed: 149)
29 Correct 1 ms 432 KB ok, most errors: 5 (allowed: 149)
30 Correct 1 ms 460 KB ok, most errors: 5 (allowed: 149)
31 Correct 1 ms 436 KB ok, most errors: 5 (allowed: 149)
32 Correct 1 ms 348 KB ok, most errors: 5 (allowed: 149)