제출 #249947

#제출 시각아이디문제언어결과실행 시간메모리
249947crackersamdjamVision Program (IOI19_vision)C++14
0 / 100
6 ms896 KiB
#ifndef ONLINE_JUDGE #define ONLINE_JUDGE #endif #include <bits/stdc++.h> using namespace std; int zero; //reeeeee #ifndef ONLINE_JUDGE template<typename T> void print(T a){std::cout<<a<<std::endl;} template<typename T,typename... Args> void print(T a, Args... args) {std::cout<<a<<' ',print(args...);} #else #include "vision.h" template<typename... Args> void print(Args... args){} #endif #ifndef ONLINE_JUDGE vector<int> all; int eval(int i){ return all[i]; } int add_and(std::vector<int> Ns){ assert(Ns.size()); int ret = 1; for(int i: Ns) ret &= all[i]; if(Ns.empty()) ret = 0; all.emplace_back(ret); return all.size()-1; } int add_or(std::vector<int> Ns){ assert(Ns.size()); int ret = 0; for(int i: Ns) ret |= all[i]; all.emplace_back(ret); return all.size()-1; } int add_xor(std::vector<int> Ns){ assert(Ns.size()); int ret = 0; for(int i: Ns) ret ^= all[i]; all.emplace_back(ret); return all.size()-1; } int add_not(int N){ all.emplace_back(!all[N]); return all.size()-1; } #else int eval(int i){ return 0; } #endif int n, m, mx; int psa[500], psa2[500], dif[500], dif2[500]; int at(int i, int j){ return i*m+j; } bool ok(int i, int j){ return i >= 0 and i < n and j >= 0 and j < m; } int go(int k){ //if dist >= k vector<int> ret = {zero}; print("try", k); for(int i = 0; i <= mx-k; i++){ if(dif[i+k]){ ret.push_back(add_and({dif[i], dif[i+k]})); //if both are different print("ora", i, i+k, eval(ret.back())); } } for(int i = 0; i <= mx-k; i++){ if(dif2[i+k]){ ret.push_back(add_and({dif2[i], dif2[i+k]})); print("orb", i, i+k, eval(ret.back())); } } return add_or(ret); } void construct_network(int _n, int _m, int k){ n = _n, m = _m; zero = add_and({0, 1, 2}); //must be 0 mx = max(n, m); psa[mx+1] = zero; print("st"); for(int i = mx; i >= 0; i--){ vector<int> v = {}; print("in", i); for(int j = 0; j <= n+m; j++){ if(ok(j, i-j)){ print(j, i-j, "-", eval(at(j, i-j))); v.push_back(at(j, i-j)); } } psa[i] = add_xor(v); dif[i] = add_xor({psa[i], psa[i+1]}); //if i is dif from i+1 print("psa", eval(psa[i]), "dif", eval(dif[i])); } psa2[mx+1] = zero; print("st2"); for(int i = mx; i >= 0; i--){ vector<int> v = {}; print("in", i); for(int j = 0; j <= n+m; j++){ if(ok(j, m-1-i+j)){ print(j, m-1-i+j); v.push_back(at(j, m-1-i+j)); } } psa2[i] = add_xor(v); dif2[i] = psa2[i]; print("psa", eval(psa2[i]), "dif", eval(dif2[i])); } int hi = go(k+1); // if k+1 (does not) work int lo = go(k); // if k works int ret = add_and({add_not(hi), lo}); print("ans", eval(hi), eval(lo), eval(ret)); } #ifndef ONLINE_JUDGE int main(){ all = {1, 0, 0, 0, 0, 1}; construct_network(2, 3, 3); cout<<all.back()<<endl; } //mt19937 g; //int randint(int l, int r){ return uniform_int_distribution<int>(l, r)(g); } //int main(int argc, char *args[]){ //// freopen("../in", "w", stdout); // int sd = argc > 1 ? atoi(args[1]) : 0; // // sd = 10; // // g = mt19937(sd); // int N = randint(1, 3), M = randint(1, 3); // if(N+M == 2) // M++; // int K = randint(1, N+M-2); // // all.resize(N*M); // // int AX = randint(0, N-1), AY = randint(0, M-1); // int BX, BY; // do{ // BX = randint(0, N-1), BY = randint(0, M-1); // } while(BX == AX and BY == AY); // // all[AX*M+AY] = all[BX*M+BY] = 1; // // cout<<N<<' '<<M<<' '<<K<<endl; // cout<<AX<<' '<<AY<<endl; // cout<<BX<<' '<<BY<<endl; // cout<<"Reeeeee "<<AX*M+AY<<' '<<BX*M+BY<<endl; // // int DIST = abs(AX-BX) + abs(AY-BY); // int ANS = DIST==K; // construct_network(N, M, K); // cout<<all.back()<<' '<<ANS<<endl; // assert(all.back() == ANS); //} #endif
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...