| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 943455 | djs100201 | Vision Program (IOI19_vision) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#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++){
vector<int>T2;
for(int k=j+a;k<H;k++){
int dif=k-j;
if(dif&a){
T2.push_back(N[k]);
}
}
if(T2.empty())continue;
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;
for(int j=0;j+a<W;j++){
vector<int>T2;
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];
if(res[i]!=-1)cout<<i<<' '<<B[res[i]]<<endl;
}
}
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;
}