oj.uz

Submission #379358

# Submission time Handle Problem Language Result Execution time Memory
379358 2021-03-18T02:47:51 Z Thistle Vision Program (IOI19_vision) C++14
66 / 100
 33 ms 3048 KB 
#include "vision.h"
#include<bits/stdc++.h>
#include<fstream>
using namespace std;

using ll=long long;
using H=pair<ll, ll>;
using vi=vector<ll>;
#define vec vector
#define rng(i,a,b) for(int (i)=(a);(i)<(b);(i)++)
#define rep(i,n) rng((i),(0),(n))
#define fs first
#define sc second
#define all(a) (a).begin(),(a).end()
#define siz(a) ll((a).size())
#define pb emplace_back

void construct_network(int H, int W, int K) {
	int h=H,w=W,k=K;
	int num=h*w;
	if(H*W*2+1<=10000){
		vec<int>tmp;
		rep(i,h)rep(j,w){
			//kyori ga k no chouten wo rekkyo
			vec<int>v;
			rep(x,h)rep(y,w){
				if(abs(x-i)+abs(y-j)==k){
					v.pb(x*w+y);
				}
			}
			if(siz(v)>0){
				add_xor(v);num++;
				add_and(vec<int>{num-1,i*w+j});num++;
				tmp.pb(num-1);
			}
		}
		add_or(tmp);
	}
	else if(K==1){
		rep(i,h){
			vec<int>v;
			rep(j,w) v.pb(i*w+j);
			add_or(v);num++;
		}
		rep(j,w){
			vec<int>v;
			rep(i,h) v.pb(i*w+j);
			add_or(v);num++;
		}

		int t=num;
		vec<int>tmp;
		rep(i,h){
			vec<int>v;v.pb(h*w+i);
			if(i!=0) v.pb(num-1);
			add_or(v);num++;
		}
		for(int i=h-1;i>=0;i--){
			vec<int>v;v.pb(h*w+i);
			if(i!=h-1) v.pb(num-1);
			add_or(v);num++;
		}
		rng(i,1,h-1){
			add_and({t+i-1,t+h+(h-i-2)});num++;
			tmp.pb(num-1);
		}

		t=num;
		rep(i,w){
			vec<int>v;v.pb(h*w+h+i);
			if(i!=0) v.pb(num-1);
			add_or(v);num++;
		}
		for(int i=w-1;i>=0;i--){
			vec<int>v;v.pb(h*w+h+i);
			if(i!=w-1) v.pb(num-1);
			add_or(v);num++;
		}
		rng(i,1,w-1){
			add_and({t+i-1,t+w+(w-i-2)});num++;
			tmp.pb(num-1);
		}

		t=num;
		auto F=[&](vec<int>v){
			add_xor(v);num++;
			add_not(num-1);num++;
			add_or(v);num++;
			add_and({num-1,num-2});num++;
			tmp.pb(num-1);
		};
		rng(i,1,h){
			vec<int>v;
			for(int k=0;k<w&&i-k>=0;k++){
				v.pb((i-k)*w+k);
			}
			F(v);
		}
		rep(i,w-1){
			vec<int>v;
			for(int k=0;h-1-k>=0&&i+k<w;k++){
				v.pb((h-1-k)*w+(i+k));
			}
			F(v);
		}
		rep(i,h-1){
			vec<int>v;
			for(int k=0;i+k<h&&k<w;k++){
				v.pb((i+k)*w+k);
			}
			F(v);
		}
		rep(i,w-1){
			vec<int>v;
			for(int k=0;k<h&&i+k<w;k++){
				v.pb((k)*w+(i+k));
			}
			F(v);
		}
		add_or(tmp);num++;
		add_not(num-1);
	}
	else{
		vec<int>v;
		rep(i,h)rep(j,w){
			if(i+j==k) v.pb(i*w+j);
		}
		add_or(v);
	}

}

Compilation message

vision.cpp: In function 'void construct_network(int, int, int)':
vision.cpp:10:28: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   10 | #define rng(i,a,b) for(int (i)=(a);(i)<(b);(i)++)
      |                            ^
vision.cpp:11:18: note: in expansion of macro 'rng'
   11 | #define rep(i,n) rng((i),(0),(n))
      |                  ^~~
vision.cpp:23:3: note: in expansion of macro 'rep'
   23 |   rep(i,h)rep(j,w){
      |   ^~~
vision.cpp:10:28: warning: unnecessary parentheses in declaration of 'j' [-Wparentheses]
   10 | #define rng(i,a,b) for(int (i)=(a);(i)<(b);(i)++)
      |                            ^
vision.cpp:11:18: note: in expansion of macro 'rng'
   11 | #define rep(i,n) rng((i),(0),(n))
      |                  ^~~
vision.cpp:23:11: note: in expansion of macro 'rep'
   23 |   rep(i,h)rep(j,w){
      |           ^~~
vision.cpp:10:28: warning: unnecessary parentheses in declaration of 'x' [-Wparentheses]
   10 | #define rng(i,a,b) for(int (i)=(a);(i)<(b);(i)++)
      |                            ^
vision.cpp:11:18: note: in expansion of macro 'rng'
   11 | #define rep(i,n) rng((i),(0),(n))
      |                  ^~~
vision.cpp:26:4: note: in expansion of macro 'rep'
   26 |    rep(x,h)rep(y,w){
      |    ^~~
vision.cpp:10:28: warning: unnecessary parentheses in declaration of 'y' [-Wparentheses]
   10 | #define rng(i,a,b) for(int (i)=(a);(i)<(b);(i)++)
      |                            ^
vision.cpp:11:18: note: in expansion of macro 'rng'
   11 | #define rep(i,n) rng((i),(0),(n))
      |                  ^~~
vision.cpp:26:12: note: in expansion of macro 'rep'
   26 |    rep(x,h)rep(y,w){
      |            ^~~
vision.cpp:10:28: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   10 | #define rng(i,a,b) for(int (i)=(a);(i)<(b);(i)++)
      |                            ^
vision.cpp:11:18: note: in expansion of macro 'rng'
   11 | #define rep(i,n) rng((i),(0),(n))
      |                  ^~~
vision.cpp:40:3: note: in expansion of macro 'rep'
   40 |   rep(i,h){
      |   ^~~
vision.cpp:10:28: warning: unnecessary parentheses in declaration of 'j' [-Wparentheses]
   10 | #define rng(i,a,b) for(int (i)=(a);(i)<(b);(i)++)
      |                            ^
vision.cpp:11:18: note: in expansion of macro 'rng'
   11 | #define rep(i,n) rng((i),(0),(n))
      |                  ^~~
vision.cpp:42:4: note: in expansion of macro 'rep'
   42 |    rep(j,w) v.pb(i*w+j);
      |    ^~~
vision.cpp:10:28: warning: unnecessary parentheses in declaration of 'j' [-Wparentheses]
   10 | #define rng(i,a,b) for(int (i)=(a);(i)<(b);(i)++)
      |                            ^
vision.cpp:11:18: note: in expansion of macro 'rng'
   11 | #define rep(i,n) rng((i),(0),(n))
      |                  ^~~
vision.cpp:45:3: note: in expansion of macro 'rep'
   45 |   rep(j,w){
      |   ^~~
vision.cpp:10:28: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   10 | #define rng(i,a,b) for(int (i)=(a);(i)<(b);(i)++)
      |                            ^
vision.cpp:11:18: note: in expansion of macro 'rng'
   11 | #define rep(i,n) rng((i),(0),(n))
      |                  ^~~
vision.cpp:47:4: note: in expansion of macro 'rep'
   47 |    rep(i,h) v.pb(i*w+j);
      |    ^~~
vision.cpp:10:28: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   10 | #define rng(i,a,b) for(int (i)=(a);(i)<(b);(i)++)
      |                            ^
vision.cpp:11:18: note: in expansion of macro 'rng'
   11 | #define rep(i,n) rng((i),(0),(n))
      |                  ^~~
vision.cpp:53:3: note: in expansion of macro 'rep'
   53 |   rep(i,h){
      |   ^~~
vision.cpp:10:28: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   10 | #define rng(i,a,b) for(int (i)=(a);(i)<(b);(i)++)
      |                            ^
vision.cpp:63:3: note: in expansion of macro 'rng'
   63 |   rng(i,1,h-1){
      |   ^~~
vision.cpp:10:28: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   10 | #define rng(i,a,b) for(int (i)=(a);(i)<(b);(i)++)
      |                            ^
vision.cpp:11:18: note: in expansion of macro 'rng'
   11 | #define rep(i,n) rng((i),(0),(n))
      |                  ^~~
vision.cpp:69:3: note: in expansion of macro 'rep'
   69 |   rep(i,w){
      |   ^~~
vision.cpp:10:28: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   10 | #define rng(i,a,b) for(int (i)=(a);(i)<(b);(i)++)
      |                            ^
vision.cpp:79:3: note: in expansion of macro 'rng'
   79 |   rng(i,1,w-1){
      |   ^~~
vision.cpp:10:28: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   10 | #define rng(i,a,b) for(int (i)=(a);(i)<(b);(i)++)
      |                            ^
vision.cpp:92:3: note: in expansion of macro 'rng'
   92 |   rng(i,1,h){
      |   ^~~
vision.cpp:10:28: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   10 | #define rng(i,a,b) for(int (i)=(a);(i)<(b);(i)++)
      |                            ^
vision.cpp:11:18: note: in expansion of macro 'rng'
   11 | #define rep(i,n) rng((i),(0),(n))
      |                  ^~~
vision.cpp:99:3: note: in expansion of macro 'rep'
   99 |   rep(i,w-1){
      |   ^~~
vision.cpp:10:28: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   10 | #define rng(i,a,b) for(int (i)=(a);(i)<(b);(i)++)
      |                            ^
vision.cpp:11:18: note: in expansion of macro 'rng'
   11 | #define rep(i,n) rng((i),(0),(n))
      |                  ^~~
vision.cpp:106:3: note: in expansion of macro 'rep'
  106 |   rep(i,h-1){
      |   ^~~
vision.cpp:10:28: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   10 | #define rng(i,a,b) for(int (i)=(a);(i)<(b);(i)++)
      |                            ^
vision.cpp:11:18: note: in expansion of macro 'rng'
   11 | #define rep(i,n) rng((i),(0),(n))
      |                  ^~~
vision.cpp:113:3: note: in expansion of macro 'rep'
  113 |   rep(i,w-1){
      |   ^~~
vision.cpp:10:28: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   10 | #define rng(i,a,b) for(int (i)=(a);(i)<(b);(i)++)
      |                            ^
vision.cpp:11:18: note: in expansion of macro 'rng'
   11 | #define rep(i,n) rng((i),(0),(n))
      |                  ^~~
vision.cpp:125:3: note: in expansion of macro 'rep'
  125 |   rep(i,h)rep(j,w){
      |   ^~~
vision.cpp:10:28: warning: unnecessary parentheses in declaration of 'j' [-Wparentheses]
   10 | #define rng(i,a,b) for(int (i)=(a);(i)<(b);(i)++)
      |                            ^
vision.cpp:11:18: note: in expansion of macro 'rng'
   11 | #define rep(i,n) rng((i),(0),(n))
      |                  ^~~
vision.cpp:125:11: note: in expansion of macro 'rep'
  125 |   rep(i,h)rep(j,w){
      |           ^~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 1 ms 364 KB Output is correct
9 Correct 1 ms 364 KB Output is correct
10 Correct 1 ms 364 KB Output is correct
11 Correct 1 ms 364 KB Output is correct
12 Correct 1 ms 364 KB Output is correct
13 Correct 1 ms 364 KB Output is correct
14 Correct 1 ms 364 KB Output is correct
15 Correct 1 ms 364 KB Output is correct
16 Correct 1 ms 364 KB Output is correct
17 Correct 1 ms 364 KB Output is correct
18 Correct 1 ms 364 KB Output is correct

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 1 ms 364 KB Output is correct
9 Correct 1 ms 364 KB Output is correct
10 Correct 1 ms 364 KB Output is correct
11 Correct 1 ms 364 KB Output is correct
12 Correct 1 ms 364 KB Output is correct
13 Correct 1 ms 364 KB Output is correct
14 Correct 1 ms 364 KB Output is correct
15 Correct 1 ms 364 KB Output is correct
16 Correct 1 ms 364 KB Output is correct
17 Correct 1 ms 364 KB Output is correct
18 Correct 1 ms 364 KB Output is correct
19 Correct 1 ms 364 KB Output is correct
20 Correct 1 ms 364 KB Output is correct
21 Correct 1 ms 364 KB Output is correct
22 Correct 1 ms 364 KB Output is correct
23 Correct 1 ms 364 KB Output is correct
24 Correct 1 ms 364 KB Output is correct
25 Correct 1 ms 364 KB Output is correct
26 Correct 1 ms 364 KB Output is correct
27 Correct 1 ms 364 KB Output is correct

Subtask #3
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 1 ms 364 KB Output is correct
9 Correct 1 ms 364 KB Output is correct
10 Correct 1 ms 364 KB Output is correct
11 Correct 1 ms 364 KB Output is correct
12 Correct 1 ms 364 KB Output is correct
13 Correct 1 ms 364 KB Output is correct
14 Correct 1 ms 364 KB Output is correct
15 Correct 1 ms 364 KB Output is correct
16 Correct 1 ms 364 KB Output is correct
17 Correct 1 ms 364 KB Output is correct
18 Correct 1 ms 364 KB Output is correct
19 Correct 1 ms 364 KB Output is correct
20 Correct 1 ms 364 KB Output is correct
21 Correct 1 ms 364 KB Output is correct
22 Correct 1 ms 364 KB Output is correct
23 Correct 1 ms 364 KB Output is correct
24 Correct 1 ms 364 KB Output is correct
25 Correct 1 ms 364 KB Output is correct
26 Correct 1 ms 364 KB Output is correct
27 Correct 1 ms 364 KB Output is correct
28 Correct 8 ms 620 KB Output is correct
29 Correct 1 ms 364 KB Output is correct
30 Correct 1 ms 364 KB Output is correct
31 Correct 1 ms 364 KB Output is correct
32 Correct 2 ms 364 KB Output is correct
33 Correct 3 ms 492 KB Output is correct
34 Correct 6 ms 620 KB Output is correct
35 Correct 5 ms 620 KB Output is correct
36 Correct 3 ms 364 KB Output is correct
37 Correct 1 ms 364 KB Output is correct

Subtask #4
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 1 ms 364 KB Output is correct
9 Correct 1 ms 364 KB Output is correct
10 Correct 1 ms 364 KB Output is correct
11 Correct 1 ms 364 KB Output is correct
12 Correct 1 ms 364 KB Output is correct
13 Correct 1 ms 364 KB Output is correct
14 Correct 1 ms 364 KB Output is correct
15 Correct 1 ms 364 KB Output is correct
16 Correct 1 ms 364 KB Output is correct
17 Correct 1 ms 364 KB Output is correct
18 Correct 1 ms 364 KB Output is correct
19 Correct 1 ms 364 KB Output is correct
20 Correct 1 ms 364 KB Output is correct
21 Correct 1 ms 364 KB Output is correct
22 Correct 1 ms 364 KB Output is correct
23 Correct 1 ms 364 KB Output is correct
24 Correct 1 ms 364 KB Output is correct
25 Correct 1 ms 364 KB Output is correct
26 Correct 1 ms 364 KB Output is correct
27 Correct 1 ms 364 KB Output is correct
28 Correct 8 ms 620 KB Output is correct
29 Correct 1 ms 364 KB Output is correct
30 Correct 1 ms 364 KB Output is correct
31 Correct 1 ms 364 KB Output is correct
32 Correct 2 ms 364 KB Output is correct
33 Correct 3 ms 492 KB Output is correct
34 Correct 6 ms 620 KB Output is correct
35 Correct 5 ms 620 KB Output is correct
36 Correct 3 ms 364 KB Output is correct
37 Correct 1 ms 364 KB Output is correct
38 Incorrect 1 ms 364 KB on inputs (8, 61), (22, 97), expected 1, but computed 0
39 Halted 0 ms 0 KB -

Subtask #5
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 2 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 1 ms 364 KB Output is correct
9 Correct 1 ms 364 KB Output is correct
10 Correct 1 ms 364 KB Output is correct
11 Correct 1 ms 364 KB Output is correct
12 Correct 1 ms 364 KB Output is correct
13 Correct 1 ms 364 KB Output is correct
14 Correct 1 ms 364 KB Output is correct
15 Correct 1 ms 364 KB Output is correct
16 Correct 1 ms 364 KB Output is correct
17 Correct 1 ms 364 KB Output is correct
18 Correct 1 ms 364 KB Output is correct
19 Correct 1 ms 364 KB Output is correct
20 Correct 1 ms 364 KB Output is correct
21 Correct 1 ms 364 KB Output is correct
22 Correct 1 ms 364 KB Output is correct

Subtask #6
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 17 ms 872 KB Output is correct
4 Correct 31 ms 1896 KB Output is correct
5 Correct 26 ms 1384 KB Output is correct
6 Correct 16 ms 748 KB Output is correct
7 Correct 11 ms 364 KB Output is correct
8 Correct 6 ms 876 KB Output is correct
9 Correct 1 ms 364 KB Output is correct
10 Correct 1 ms 364 KB Output is correct
11 Correct 1 ms 364 KB Output is correct
12 Correct 1 ms 364 KB Output is correct
13 Correct 1 ms 364 KB Output is correct
14 Correct 1 ms 364 KB Output is correct
15 Correct 1 ms 364 KB Output is correct
16 Correct 1 ms 364 KB Output is correct
17 Correct 1 ms 364 KB Output is correct
18 Correct 1 ms 364 KB Output is correct
19 Correct 1 ms 364 KB Output is correct
20 Correct 17 ms 1772 KB Output is correct
21 Correct 1 ms 364 KB Output is correct
22 Correct 1 ms 364 KB Output is correct
23 Correct 1 ms 364 KB Output is correct
24 Correct 16 ms 1772 KB Output is correct
25 Correct 1 ms 364 KB Output is correct
26 Correct 1 ms 364 KB Output is correct
27 Correct 33 ms 3048 KB Output is correct
28 Correct 1 ms 364 KB Output is correct
29 Correct 1 ms 364 KB Output is correct
30 Correct 1 ms 364 KB Output is correct
31 Correct 1 ms 364 KB Output is correct
32 Correct 1 ms 364 KB Output is correct
33 Correct 1 ms 364 KB Output is correct

Subtask #7
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 3048 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 16 ms 864 KB Output is correct
4 Correct 7 ms 876 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 16 ms 1772 KB Output is correct
8 Correct 16 ms 1772 KB Output is correct
9 Correct 30 ms 3048 KB Output is correct
10 Correct 1 ms 364 KB Output is correct
11 Correct 1 ms 364 KB Output is correct

Subtask #8
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 1 ms 364 KB Output is correct
9 Correct 1 ms 364 KB Output is correct
10 Correct 1 ms 364 KB Output is correct
11 Correct 1 ms 364 KB Output is correct
12 Correct 1 ms 364 KB Output is correct
13 Correct 1 ms 364 KB Output is correct
14 Correct 1 ms 364 KB Output is correct
15 Correct 1 ms 364 KB Output is correct
16 Correct 1 ms 364 KB Output is correct
17 Correct 1 ms 364 KB Output is correct
18 Correct 1 ms 364 KB Output is correct
19 Correct 1 ms 364 KB Output is correct
20 Correct 1 ms 364 KB Output is correct
21 Correct 1 ms 364 KB Output is correct
22 Correct 1 ms 364 KB Output is correct
23 Correct 1 ms 364 KB Output is correct
24 Correct 1 ms 364 KB Output is correct
25 Correct 1 ms 364 KB Output is correct
26 Correct 1 ms 364 KB Output is correct
27 Correct 1 ms 364 KB Output is correct
28 Correct 8 ms 620 KB Output is correct
29 Correct 1 ms 364 KB Output is correct
30 Correct 1 ms 364 KB Output is correct
31 Correct 1 ms 364 KB Output is correct
32 Correct 2 ms 364 KB Output is correct
33 Correct 3 ms 492 KB Output is correct
34 Correct 6 ms 620 KB Output is correct
35 Correct 5 ms 620 KB Output is correct
36 Correct 3 ms 364 KB Output is correct
37 Correct 1 ms 364 KB Output is correct
38 Incorrect 1 ms 364 KB on inputs (8, 61), (22, 97), expected 1, but computed 0
39 Halted 0 ms 0 KB -