답안 #894328

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
894328 2023-12-28T05:46:57 Z KaleemRazaSyed Vision Program (IOI19_vision) C++17
0 / 100
14 ms 1688 KB
#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); 
      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);
  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);
      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);
  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

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++)
      |                  ~~^~~~~~~~~~~
# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Incorrect 0 ms 348 KB on inputs (1, 0), (2, 0), expected 1, but computed 0
4 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Incorrect 0 ms 348 KB on inputs (1, 0), (2, 0), expected 1, but computed 0
4 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Incorrect 0 ms 348 KB on inputs (1, 0), (2, 0), expected 1, but computed 0
4 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Incorrect 0 ms 348 KB on inputs (1, 0), (2, 0), expected 1, but computed 0
4 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 5 ms 792 KB Output is correct
3 Correct 4 ms 600 KB Output is correct
4 Correct 1 ms 344 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 3 ms 604 KB Output is correct
7 Incorrect 3 ms 604 KB on inputs (65, 0), (198, 0), expected 1, but computed 0
8 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 2 ms 604 KB Output is correct
4 Correct 2 ms 624 KB Output is correct
5 Correct 3 ms 604 KB Output is correct
6 Correct 2 ms 604 KB Output is correct
7 Correct 2 ms 348 KB Output is correct
8 Correct 3 ms 712 KB Output is correct
9 Correct 5 ms 1120 KB Output is correct
10 Correct 5 ms 860 KB Output is correct
11 Correct 4 ms 856 KB Output is correct
12 Correct 2 ms 604 KB Output is correct
13 Correct 1 ms 348 KB Output is correct
14 Correct 5 ms 856 KB Output is correct
15 Correct 3 ms 604 KB Output is correct
16 Correct 1 ms 348 KB Output is correct
17 Correct 1 ms 344 KB Output is correct
18 Correct 4 ms 604 KB Output is correct
19 Correct 1 ms 348 KB Output is correct
20 Correct 8 ms 1068 KB Output is correct
21 Incorrect 13 ms 1688 KB on inputs (0, 0), (199, 99), expected 0, but computed 1
22 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Incorrect 14 ms 1484 KB on inputs (126, 120), (176, 169), expected 0, but computed 1
2 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Incorrect 0 ms 348 KB on inputs (1, 0), (2, 0), expected 1, but computed 0
4 Halted 0 ms 0 KB -