oj.uz

Submission #943445

# Submission time Handle Problem Language Result Execution time Memory
943445 2024-03-11T13:20:14 Z djs100201 Vision Program (IOI19_vision) C++17
0 / 100
 74 ms 10436 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,T2;
        for(int j=0;j+a<H;j++){
            for(int k=j+a;k<H;k++){
                int dif=k-j;
                if(dif&a)T2.push_back(N[k]);
            }
            int x=base++;
            add_or(T2);
            Ns={N[j],x};
            T.push_back(base++);
            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,T2;
        for(int j=0;j+a<W;j++){
            for(int k=j+a;k<W;k++){
                int dif=k-j;
                if(dif&a)T2.push_back(M[k]);
            }
            int x=base++;
            add_or(T2);
            Ns={M[j],x};
            T.push_back(base++);
            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
0 / 10.0

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

Subtask #2
0 / 11.0

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

Subtask #3
0 / 11.0

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

Subtask #4
0 / 15.0

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

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 7516 KB WA in grader: Too many inputs
2 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 69 ms 10436 KB Output is correct
4 Incorrect 74 ms 10360 KB on inputs (0, 0), (2, 28), expected 0, but computed 1
5 Halted 0 ms 0 KB -

Subtask #7
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 8476 KB WA in grader: Too many inputs
2 Halted 0 ms 0 KB -

Subtask #8
0 / 19.0

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