Submission #425241

#	Time	Username	Problem	Language	Result	Execution time	Memory
425241		oleh1421	Vision Program (IOI19_vision)	C++17	100 / 100	67 ms	5060 KiB

vision

//#include "grader.cpp"

#include "vision.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
map<int,vector<int>>vr,vc;
void construct_network(int H, int W, int K) {

    int ind=H*W-1;
    for (int i=0;i<H;i++){
        for (int j=0;j<W;j++){
            vr[i-j].push_back(i*W+j);
            vc[i+j].push_back(i*W+j);
        }
    }
    vector<pair<int,int> >r;
    for (auto cur:vr){
        add_xor(cur.second);
        r.push_back({cur.first,++ind});
    }
    vector<pair<int,int> >c;
    for (auto cur:vc){
        add_xor(cur.second);
        c.push_back({cur.first,++ind});
    }
    vector<int>Lr,Er;
    for (int i=0;i<r.size();i++){
        vector<int>v;
        for (int j=i;j<r.size() && r[j].first-r[i].first<K;j++){
            v.push_back(r[j].second);
        }
        add_or(v);
        int Or=++ind;
        add_xor(v);
        int Xr=++ind;
        add_not(Xr);
        Xr=++ind;
        add_and({Or,Xr});
        Lr.push_back(++ind);
        int pos=-1;
        for (int j=i;j<r.size();j++){
            if (r[j].first-r[i].first==K){
                pos=j;
                break;
            }
        }
        if (pos!=-1) {
            add_and({r[i].second,r[pos].second});
            Er.push_back(++ind);
//            cout<<i<<" "<<r[i].first<<" "<<ind<<" "<<r[i].second<<" "<<r[pos].second<<endl;
        }
    }
    vector<int>askr;
    for (auto cur:r) askr.push_back(cur.second);
    add_or(askr);
    ++ind;
    add_not(ind);
    ++ind;
    Lr.push_back(ind);

    vector<int>Lc,Ec;
    for (int i=0;i<c.size();i++){
        vector<int>v;
        for (int j=i;j<c.size() && c[j].first-c[i].first<K;j++){
            v.push_back(c[j].second);
//            cout<<c[j].first<<" ";
        }
//        cout<<endl;

        add_or(v);
        int Or=++ind;
        add_xor(v);
        int Xr=++ind;
        add_not(Xr);
        Xr=++ind;
        add_and({Or,Xr});
        Lc.push_back(++ind);
        int pos=-1;
        for (int j=i;j<c.size();j++){
            if (c[j].first-c[i].first==K){
                pos=j;
                break;
            }
        }
        if (pos!=-1) {
            add_and({c[i].second,c[pos].second});
            Ec.push_back(++ind);
//            cout<<i<<" "<<c[i].first<<" "<<ind<<" "<<c[i].second<<" "<<c[pos].second<<endl;
        }
    }
    vector<int>askc;
    for (auto cur:c) askc.push_back(cur.second);
    add_or(askc);
    ++ind;
    add_not(ind);
    ++ind;
    Lc.push_back(ind);
    add_or(Lr);
    int OrA=++ind;
    add_or(Er);
    int OrB=++ind;
    add_or(Lc);
    int OrC=++ind;
    add_or(Ec);
    int OrD=++ind;
    add_and({OrA,OrD});
    int A=++ind;
    add_and({OrB,OrC});
    int B=++ind;
    add_and({OrB,OrD});
    int C=++ind;

    add_or({A,B,C});
    ind++;
//    cout<<OrA<<" "<<OrB<<" "<<OrC<<" "<<OrD<<" "<<A<<" "<<B<<" "<<C<<endl;




}
/**
2 3 3
0 0 0 1
0 0 0 2
0 0 1 0
0 0 1 1
0 0 1 2
0 1 0 2
0 1 1 0
0 1 1 1
0 1 1 2
0 2 1 0
0 2 1 1
0 2 1 2
1 0 1 1
1 0 1 2
1 1 1 2
-1

**/

Compilation message (stderr)

vision.cpp: In function 'void construct_network(int, int, int)':
vision.cpp:28:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   28 |     for (int i=0;i<r.size();i++){
      |                  ~^~~~~~~~~
vision.cpp:30:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   30 |         for (int j=i;j<r.size() && r[j].first-r[i].first<K;j++){
      |                      ~^~~~~~~~~
vision.cpp:42:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   42 |         for (int j=i;j<r.size();j++){
      |                      ~^~~~~~~~~
vision.cpp:63:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   63 |     for (int i=0;i<c.size();i++){
      |                  ~^~~~~~~~~
vision.cpp:65:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   65 |         for (int j=i;j<c.size() && c[j].first-c[i].first<K;j++){
      |                      ~^~~~~~~~~
vision.cpp:80:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   80 |         for (int j=i;j<c.size();j++){
      |                      ~^~~~~~~~~

• Subtask 1: 10 / 10
• Subtask 2: 11 / 11
• Subtask 3: 11 / 11
• Subtask 4: 15 / 15
• Subtask 5: 12 / 12
• Subtask 6: 8 / 8
• Subtask 7: 14 / 14
• Subtask 8: 19 / 19