Submission #894331

#	Time	Username	Problem	Language	Result	Execution time	Memory
894331		KaleemRazaSyed	Vision Program (IOI19_vision)	C++17	100 / 100	27 ms	3156 KiB

vision

#include<bits/stdc++.h>

using namespace std;

int add_and(vector<int> Ns);
int add_or(vector<int> Ns);
int add_xor(vector<int> Ns);
int add_not(int N);

// Robot Memory :
// H * W|---cnt1---|---cnt2---|---cnt3---|---cnt4---|---cnt3---|---cnt4---|---cnt5---|---cnt6---|---2---|---2---|---1---|---1---|---1---|
// grid |d1..or..d1|d2..or..d2|or1....or1|or2....or2|xor1..xor1|xor2..xor2|&1......&1|&2......&2|xor.xor|or..xor|&orxor.|..orr..|&orrxor|


void construct_network(int H, int W, int K)
{  
  vector<pair<int,int> > d1, d2;
  for(int i = 0; i < H; i++)
    for(int j = 0; j < W; j++)
      {
	d1.push_back({i + j, i * W + j});
	d2.push_back({i - j, i * W + j});
      }

  sort(d1.begin(), d1.end());
  sort(d2.begin(), d2.end());

  int cnt1 = 0, cnt2 = 0;
  vector<int> q;
  for(int i = 0; i < d1.size(); i++)
    {
      if(q.size() and d1[i-1].first != d1[i].first)
	{
	  cnt1++;
	  add_or(q);
	  q.clear();
	}
      q.push_back(d1[i].second);
    }
  cnt1++;
  add_or(q);
  q.clear();

  for(int i = 0; i < d2.size(); i++)
    {
      if(q.size() and d2[i-1].first != d2[i].first)
	{
	  cnt2++;
	  add_or(q);
	  q.clear();
	}
      q.push_back(d2[i].second);
    }
  cnt2++;
  add_or(q);
  q.clear();

  vector<int> D;
  // or
  int cnt3 = 1;
  for(int i = 0; i <= K; i++)
    D.push_back(H * W + i);

  for(int k = K + 1; k < cnt1; k++)
    {
      cnt3++;
      add_or(D);
      D.erase(D.begin());
      D.push_back(H * W + k);
    }
  add_or(D);

  D.clear();
  for(int i = 0; i <= K; i++)
    D.push_back(H * W + cnt1 + i);
  int cnt4 = 1;
  for(int k = K + 1; k < cnt2; k++)
    {
      cnt4++;
      add_or(D);
      D.erase(D.begin());
      D.push_back(H * W + k + cnt1);
    }
  add_or(D);
  D.clear();
  // xor
  for(int i = 0; i <= K; i++)
    D.push_back(H * W + i);
  
  for(int k = K + 1; k < cnt1; k++)
    {
      D.push_back(H * W + cnt1 + cnt2 + k - K - 1); 
      add_xor(D);
      D.pop_back();
      
      D.erase(D.begin());
      D.push_back(H * W + k);
    }
  D.push_back(H * W + cnt1 + cnt2 + cnt1 - K - 1);
  add_xor(D);
  D.clear();

  for(int i = 0; i <= K; i++)
    D.push_back(H * W + cnt1 + i);

  for(int k = K + 1; k < cnt2; k++)
    {
      D.push_back(H * W + cnt1 + cnt2 + cnt3 + k - K - 1);
      add_xor(D);
      D.pop_back();
      
      D.erase(D.begin());
      D.push_back(H * W + k + cnt1);
    }
  D.push_back(H * W + cnt1 + cnt2 + cnt3 + cnt2 - K - 1);
  add_xor(D);
  D.clear(); 

  int cnt5 = 0;
  for(int i = 0; i < cnt1 - K; i ++)
    {
      cnt5++;
      add_and({H * W + i, H * W + i + K});
    }

  int cnt6 = 0;
  for(int i = 0; i < cnt2 - K; i++)
    {
      cnt6++;
      add_and({H * W + cnt1 + i, H * W + cnt1 + i + K});
    }

  vector<int> Xors;
  for(int i = 0; i < cnt1; i++)
    Xors.push_back(H * W + i);
  add_xor(Xors);
  Xors.clear();
  for(int i = 0; i < cnt2; i++)
    Xors.push_back(H * W + cnt1 + i);
  add_xor(Xors);
  
  D.clear();
  for(int i = 0; i < cnt3; i++)
    D.push_back({H * W + cnt1 + cnt2 + cnt3 + cnt4 + i});
  D.push_back(H * W + cnt1 + cnt2 + cnt3 + cnt4 + cnt3 + cnt4 + cnt5 + cnt6);
  add_or(D);

  D.clear();
  for(int i = 0; i < cnt4; i++)
    D.push_back({H * W + cnt1 + cnt2 + cnt3 + cnt4 + cnt3 + i});
  D.push_back(H * W + cnt1 + cnt2 + cnt3 + cnt4 + cnt3 + cnt4 + cnt5 + cnt6 + 1);
  add_or(D);

  add_and({H * W + cnt1 + cnt2 + cnt3 + cnt4 + cnt3 + cnt4 + cnt5 + cnt6 + 2, H * W + cnt1 + cnt2 + cnt3 + cnt4 + cnt3 + cnt4 + cnt5 + cnt6 + 3});

  D.clear();
  for(int i = 0; i < cnt5; i++)
    D.push_back(H * W + cnt1 + cnt2 + cnt3 + cnt4 + cnt3 + cnt4 + i);
  for(int i = 0; i < cnt6; i++)
    D.push_back(H * W + cnt1 + cnt2 + cnt3 + cnt4 + cnt3 + cnt4 + cnt5 + i);
  add_or(D);
  
  int cnt = H * W + cnt1 + cnt2 + cnt3 + cnt4 + cnt3 + cnt4 + cnt5 + cnt6 + 4;
  add_and({cnt, cnt + 1});
  //cout << H * W << ' ' << cnt1 << ' ' << cnt2 << ' ' << cnt3 << ' ' << cnt4 << ' ' << cnt3 << ' ' << cnt4 << ' ' << cnt5 << ' ' << cnt6 << ' ' << 4 << endl;
}

Compilation message (stderr)

vision.cpp: In function 'void construct_network(int, int, int)':
vision.cpp:30:20: 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 i = 0; i < d1.size(); i++)
      |                  ~~^~~~~~~~~~~
vision.cpp:44:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   44 |   for(int i = 0; i < d2.size(); i++)
      |                  ~~^~~~~~~~~~~

• 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