oj.uz

Submission #942388

# Submission time Handle Problem Language Result Execution time Memory
942388 2024-03-10T14:49:53 Z djs100201 Vision Program (IOI19_vision) C++17
24 / 100
 9 ms 3512 KB 
#include<bits/stdc++.h>
#include "vision.h"
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("avx2")
#define all(v) v.begin(),v.end()
using namespace std;
using ll = long long;
using P = pair<ll, ll>;
using PP = pair<ll, P>;
const ll n_ =2024+100, inf = (ll)2e9 * (ll)1e9 + 7, mod = 998244353;
ll n, m, tc = 1, a, b, c, d, sum, x, y, z, base, ans, k;
ll gcd(ll x,ll y){
	if(!y)return x;
	return gcd(y,x%y);
}
int idx[n_][n_];
void construct_network(int H, int W, int K) {
	vector<int> Ns;
    for(int i=0;i<H;i++)
        for(int j=0;j<W;j++)idx[i][j]=base++;
    //0 1 2 3 .. W-1
    //
    vector<int>N(H),M(W);
    for(int i=0;i<H;i++){
        N[i]=base++;
        for(int j=0;j<W;j++)Ns.push_back(W*i+j);
        add_or(Ns);
        Ns.clear();
    }
    for(int i=0;i<W;i++){
        M[i]=base++;
        for(int j=0;j<H;j++)Ns.push_back(idx[j][i]);
        add_or(Ns);
        Ns.clear();
    }
    vector<int>N2(9,-1),M2(9,-1),C(9,-1),res(9,-1);
    for(int i=0;i<9;i++){
        a=(1ll<<i);
        vector<int>T;
        for(int j=0;j+a<H;j++){
            T.push_back(base++);
            Ns={N[j],N[j+a]};
            add_and(Ns);
            Ns.clear();
        }
        if(T.empty())continue;
        N2[i]=base++;
        add_or(T);
    }
    for(int i=0;i<9;i++){
        a=(1ll<<i);
        vector<int>T;
        for(int j=0;j+a<W;j++){
            T.push_back(base++);
            Ns={M[j],M[j+a]};
            add_and(Ns);
            Ns.clear();
        }
        if(T.empty())continue;
        M2[i]=base++;
        add_or(T);
    }
    if(H>=2 && W>=2){
        res[0]=base++;
        add_xor({N2[0],M2[0]});
        C[1]=base++;
        add_and({N2[0],M2[0]});
        for(int i=1;i<9;i++){
            if(N2[i]==-1 && M2[i]==-1){
                res[i]=C[i];
                break;
            }
            if(N2[i]==-1){
                res[i]=base++;
                add_xor({M2[i],C[i]});
                C[i+1]=base++;
                add_and({M2[i],C[i]});
            }
            else if(M2[i]==-1){
                res[i]=base++;
                add_xor({N2[i],C[i]});
                C[i+1]=base++;
                add_and({N2[i],C[i]});
            }
            else{
                res[i]=base++;
                add_xor({N2[i],M2[i],C[i]});
                a=base++;
                add_and({N2[i],C[i]});
                b=base++;
                add_and({M2[i],C[i]});
                c=base++;
                add_and({N2[i],M2[i]});
                C[i+1]=base++;
                add_or({(int)a,(int)b,(int)c});
            }
        }
    }
    else if(H==1){
        for(int i=0;i<9;i++)res[i]=M2[i];
    }
    else if(W==1)for(int i=0;i<9;i++)res[i]=N2[i];
    vector<int>fin;
    for(int i=0;i<9;i++){
        if(res[i]==-1)continue;
        //cout<<i<<' '<<res[i]<<' '<<B[res[i]]<<endl;
        a=(1<<i);
        if(!(K&a)){
            add_not(res[i]);
            res[i]=base++;
        }
        fin.push_back(res[i]);
    }
    add_and(fin);
    //cout<<res[0]<<' '<<B[res[0]]<<endl; 
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 1 ms 444 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 0 ms 440 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 444 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 1 ms 348 KB Output is correct
16 Correct 1 ms 344 KB Output is correct
17 Correct 1 ms 344 KB Output is correct
18 Correct 0 ms 348 KB Output is correct

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 1 ms 444 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 0 ms 440 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 444 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 1 ms 348 KB Output is correct
16 Correct 1 ms 344 KB Output is correct
17 Correct 1 ms 344 KB Output is correct
18 Correct 0 ms 348 KB Output is correct
19 Incorrect 0 ms 348 KB on inputs (0, 0), (0, 3), expected 1, but computed 0
20 Halted 0 ms 0 KB -

Subtask #3
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 1 ms 444 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 0 ms 440 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 444 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 1 ms 348 KB Output is correct
16 Correct 1 ms 344 KB Output is correct
17 Correct 1 ms 344 KB Output is correct
18 Correct 0 ms 348 KB Output is correct
19 Incorrect 0 ms 348 KB on inputs (0, 0), (0, 3), expected 1, but computed 0
20 Halted 0 ms 0 KB -

Subtask #4
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 1 ms 444 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 0 ms 440 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 444 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 1 ms 348 KB Output is correct
16 Correct 1 ms 344 KB Output is correct
17 Correct 1 ms 344 KB Output is correct
18 Correct 0 ms 348 KB Output is correct
19 Incorrect 0 ms 348 KB on inputs (0, 0), (0, 3), expected 1, but computed 0
20 Halted 0 ms 0 KB -

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Incorrect 1 ms 580 KB on inputs (0, 0), (0, 99), expected 1, but computed 0
3 Halted 0 ms 0 KB -

Subtask #6
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 2 ms 2652 KB Output is correct
4 Incorrect 2 ms 2648 KB on inputs (0, 0), (3, 28), expected 1, but computed 0
5 Halted 0 ms 0 KB -

Subtask #7
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 3420 KB Output is correct
2 Correct 1 ms 344 KB Output is correct
3 Correct 2 ms 2652 KB Output is correct
4 Correct 2 ms 2652 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 1 ms 2652 KB Output is correct
7 Correct 5 ms 3164 KB Output is correct
8 Correct 5 ms 3164 KB Output is correct
9 Correct 8 ms 3512 KB Output is correct
10 Correct 1 ms 344 KB Output is correct
11 Correct 0 ms 344 KB Output is correct

Subtask #8
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 1 ms 444 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 0 ms 440 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 444 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 1 ms 348 KB Output is correct
16 Correct 1 ms 344 KB Output is correct
17 Correct 1 ms 344 KB Output is correct
18 Correct 0 ms 348 KB Output is correct
19 Incorrect 0 ms 348 KB on inputs (0, 0), (0, 3), expected 1, but computed 0
20 Halted 0 ms 0 KB -