oj.uz

Submission #838052

# Submission time Handle Problem Language Result Execution time Memory
838052 2023-08-26T06:57:58 Z penguinman Vision Program (IOI19_vision) C++17
100 / 100
 11 ms 1884 KB 
#include "vision.h"
#include <bits/stdc++.h>

#ifndef EVAL
#include "grader.cpp"
#endif

using std::cin;
using std::cout;
using std::vector;
using std::string;
using ll = int;
using vi = vector<ll>;
using vii = vector<vi>;
using pii = std::pair<ll,ll>;

#define rep(i,j,k) for(ll i=ll(j); i<ll(k); i++)
#define REP(i,j,k) for(ll i=ll(j); i<=ll(k); i++)
#define per(i,j,k) for(ll i=ll(j); i>=ll(k); i--)
#define ln "\n"
#define pb emplace_back
#define mp std::make_pair
#define mtp std::make_tuple
#define all(a) a.begin(),a.end()


void construct_network(int H, int W, int K) {

	vii plus(H+W-1), minus(H+W-1);
	rep(i,0,H){
		rep(j,0,W){
			ll idx = i*W+j;
			plus[i+j].pb(idx);
			minus[i-j+W-1].pb(idx);
		}
	}
	vi plus_or(H+W-1), minus_or(H+W-1);
	rep(i,0,H+W-1){
		plus_or[i] = add_or(plus[i]);
		minus_or[i] = add_or(minus[i]);
	}
	vi plus_val, minus_val;
	rep(i,0,H+W-1){
		if(i+K >= plus_or.size()) continue;
		plus_val.pb(add_and({plus_or[i], plus_or[i+K]}));
		minus_val.pb(add_and({minus_or[i], minus_or[i+K]}));
	}
	ll plus_check1 = add_or(plus_val);
	ll minus_check1 = add_or(minus_val);
	{
		ll modify = add_xor(plus_or);
		modify = add_not(modify);
		rep(i,0,H+W-1) plus_or[i] = add_and({plus_or[i], modify});
	}
	{
		ll modify = add_xor(minus_or);
		modify = add_not(modify);
		rep(i,0,H+W-1) minus_or[i] = add_and({minus_or[i], modify});
	}
	rep(i,1,H+W-1){
		plus_or[i] = add_xor({plus_or[i-1], plus_or[i]});
		minus_or[i] = add_xor({minus_or[i-1], minus_or[i]});
	}
	plus_val.clear();
	minus_val.clear();
	rep(i,0,H+W-1){
		if(i+K >= plus_or.size()) continue;
		plus_val.pb(add_and({plus_or[i], plus_or[i+K]}));
		minus_val.pb(add_and({minus_or[i], minus_or[i+K]}));
	}
	ll plus_check2 = add_or(plus_val);
	ll minus_check2 = add_or(minus_val);
	plus_check2 = add_not(plus_check2);
	minus_check2 = add_not(minus_check2);
	ll final_check1 = add_and({plus_check1, minus_check2});
	ll final_check2 = add_and({plus_check2, minus_check1});
	ll ans = add_or({final_check1, final_check2});
	return;
}

Compilation message

vision.cpp: In function 'void construct_network(int, int, int)':
vision.cpp:44:10: warning: comparison of integer expressions of different signedness: 'll' {aka 'int'} and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   44 |   if(i+K >= plus_or.size()) continue;
      |      ~~~~^~~~~~~~~~~~~~~~~
vision.cpp:67:10: warning: comparison of integer expressions of different signedness: 'll' {aka 'int'} and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   67 |   if(i+K >= plus_or.size()) continue;
      |      ~~~~^~~~~~~~~~~~~~~~~
vision.cpp:77:5: warning: unused variable 'ans' [-Wunused-variable]
   77 |  ll ans = add_or({final_check1, final_check2});
      |     ^~~

Subtask #1
10.0 / 10.0

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

Subtask #2
11.0 / 11.0

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

Subtask #3
11.0 / 11.0

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

Subtask #4
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 0 ms 212 KB Output is correct
11 Correct 1 ms 212 KB Output is correct
12 Correct 0 ms 212 KB Output is correct
13 Correct 0 ms 212 KB Output is correct
14 Correct 1 ms 212 KB Output is correct
15 Correct 1 ms 212 KB Output is correct
16 Correct 0 ms 212 KB Output is correct
17 Correct 0 ms 212 KB Output is correct
18 Correct 0 ms 212 KB Output is correct
19 Correct 0 ms 212 KB Output is correct
20 Correct 0 ms 212 KB Output is correct
21 Correct 0 ms 212 KB Output is correct
22 Correct 1 ms 212 KB Output is correct
23 Correct 0 ms 212 KB Output is correct
24 Correct 0 ms 212 KB Output is correct
25 Correct 0 ms 212 KB Output is correct
26 Correct 1 ms 232 KB Output is correct
27 Correct 0 ms 212 KB Output is correct
28 Correct 1 ms 340 KB Output is correct
29 Correct 0 ms 212 KB Output is correct
30 Correct 0 ms 212 KB Output is correct
31 Correct 1 ms 340 KB Output is correct
32 Correct 1 ms 340 KB Output is correct
33 Correct 1 ms 340 KB Output is correct
34 Correct 1 ms 340 KB Output is correct
35 Correct 1 ms 340 KB Output is correct
36 Correct 1 ms 340 KB Output is correct
37 Correct 1 ms 340 KB Output is correct
38 Correct 4 ms 724 KB Output is correct
39 Correct 1 ms 340 KB Output is correct
40 Correct 1 ms 340 KB Output is correct
41 Correct 2 ms 468 KB Output is correct
42 Correct 2 ms 468 KB Output is correct
43 Correct 3 ms 724 KB Output is correct
44 Correct 4 ms 724 KB Output is correct
45 Correct 3 ms 736 KB Output is correct
46 Correct 3 ms 724 KB Output is correct
47 Correct 3 ms 724 KB Output is correct

Subtask #5
12.0 / 12.0

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

Subtask #6
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 468 KB Output is correct
4 Correct 1 ms 468 KB Output is correct
5 Correct 1 ms 468 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 2 ms 596 KB Output is correct
9 Correct 2 ms 548 KB Output is correct
10 Correct 3 ms 596 KB Output is correct
11 Correct 2 ms 596 KB Output is correct
12 Correct 2 ms 596 KB Output is correct
13 Correct 1 ms 468 KB Output is correct
14 Correct 2 ms 468 KB Output is correct
15 Correct 1 ms 340 KB Output is correct
16 Correct 1 ms 340 KB Output is correct
17 Correct 1 ms 468 KB Output is correct
18 Correct 1 ms 468 KB Output is correct
19 Correct 1 ms 340 KB Output is correct
20 Correct 5 ms 1108 KB Output is correct
21 Correct 5 ms 1108 KB Output is correct
22 Correct 5 ms 1040 KB Output is correct
23 Correct 4 ms 980 KB Output is correct
24 Correct 5 ms 1108 KB Output is correct
25 Correct 5 ms 1092 KB Output is correct
26 Correct 4 ms 980 KB Output is correct
27 Correct 9 ms 1880 KB Output is correct
28 Correct 9 ms 1884 KB Output is correct
29 Correct 9 ms 1800 KB Output is correct
30 Correct 9 ms 1740 KB Output is correct
31 Correct 8 ms 1748 KB Output is correct
32 Correct 0 ms 212 KB Output is correct
33 Correct 0 ms 212 KB Output is correct

Subtask #7
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 1876 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 468 KB Output is correct
4 Correct 3 ms 596 KB Output is correct
5 Correct 1 ms 468 KB Output is correct
6 Correct 2 ms 468 KB Output is correct
7 Correct 5 ms 1108 KB Output is correct
8 Correct 5 ms 1108 KB Output is correct
9 Correct 9 ms 1876 KB Output is correct
10 Correct 0 ms 212 KB Output is correct
11 Correct 1 ms 212 KB Output is correct

Subtask #8
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 0 ms 212 KB Output is correct
11 Correct 1 ms 212 KB Output is correct
12 Correct 0 ms 212 KB Output is correct
13 Correct 0 ms 212 KB Output is correct
14 Correct 1 ms 212 KB Output is correct
15 Correct 1 ms 212 KB Output is correct
16 Correct 0 ms 212 KB Output is correct
17 Correct 0 ms 212 KB Output is correct
18 Correct 0 ms 212 KB Output is correct
19 Correct 0 ms 212 KB Output is correct
20 Correct 0 ms 212 KB Output is correct
21 Correct 0 ms 212 KB Output is correct
22 Correct 1 ms 212 KB Output is correct
23 Correct 0 ms 212 KB Output is correct
24 Correct 0 ms 212 KB Output is correct
25 Correct 0 ms 212 KB Output is correct
26 Correct 1 ms 232 KB Output is correct
27 Correct 0 ms 212 KB Output is correct
28 Correct 1 ms 340 KB Output is correct
29 Correct 0 ms 212 KB Output is correct
30 Correct 0 ms 212 KB Output is correct
31 Correct 1 ms 340 KB Output is correct
32 Correct 1 ms 340 KB Output is correct
33 Correct 1 ms 340 KB Output is correct
34 Correct 1 ms 340 KB Output is correct
35 Correct 1 ms 340 KB Output is correct
36 Correct 1 ms 340 KB Output is correct
37 Correct 1 ms 340 KB Output is correct
38 Correct 4 ms 724 KB Output is correct
39 Correct 1 ms 340 KB Output is correct
40 Correct 1 ms 340 KB Output is correct
41 Correct 2 ms 468 KB Output is correct
42 Correct 2 ms 468 KB Output is correct
43 Correct 3 ms 724 KB Output is correct
44 Correct 4 ms 724 KB Output is correct
45 Correct 3 ms 736 KB Output is correct
46 Correct 3 ms 724 KB Output is correct
47 Correct 3 ms 724 KB Output is correct
48 Correct 1 ms 468 KB Output is correct
49 Correct 1 ms 340 KB Output is correct
50 Correct 1 ms 468 KB Output is correct
51 Correct 1 ms 340 KB Output is correct
52 Correct 1 ms 468 KB Output is correct
53 Correct 1 ms 468 KB Output is correct
54 Correct 1 ms 340 KB Output is correct
55 Correct 1 ms 340 KB Output is correct
56 Correct 1 ms 468 KB Output is correct
57 Correct 1 ms 468 KB Output is correct
58 Correct 1 ms 340 KB Output is correct
59 Correct 1 ms 340 KB Output is correct
60 Correct 1 ms 340 KB Output is correct
61 Correct 1 ms 340 KB Output is correct
62 Correct 2 ms 468 KB Output is correct
63 Correct 1 ms 468 KB Output is correct
64 Correct 1 ms 340 KB Output is correct
65 Correct 1 ms 340 KB Output is correct
66 Correct 1 ms 340 KB Output is correct
67 Correct 1 ms 340 KB Output is correct
68 Correct 1 ms 212 KB Output is correct
69 Correct 0 ms 212 KB Output is correct
70 Correct 0 ms 212 KB Output is correct
71 Correct 0 ms 212 KB Output is correct
72 Correct 1 ms 468 KB Output is correct
73 Correct 1 ms 468 KB Output is correct
74 Correct 1 ms 468 KB Output is correct
75 Correct 1 ms 340 KB Output is correct
76 Correct 1 ms 340 KB Output is correct
77 Correct 2 ms 596 KB Output is correct
78 Correct 2 ms 548 KB Output is correct
79 Correct 3 ms 596 KB Output is correct
80 Correct 2 ms 596 KB Output is correct
81 Correct 2 ms 596 KB Output is correct
82 Correct 1 ms 468 KB Output is correct
83 Correct 2 ms 468 KB Output is correct
84 Correct 1 ms 340 KB Output is correct
85 Correct 1 ms 340 KB Output is correct
86 Correct 1 ms 468 KB Output is correct
87 Correct 1 ms 468 KB Output is correct
88 Correct 1 ms 340 KB Output is correct
89 Correct 5 ms 1108 KB Output is correct
90 Correct 5 ms 1108 KB Output is correct
91 Correct 5 ms 1040 KB Output is correct
92 Correct 4 ms 980 KB Output is correct
93 Correct 5 ms 1108 KB Output is correct
94 Correct 5 ms 1092 KB Output is correct
95 Correct 4 ms 980 KB Output is correct
96 Correct 9 ms 1880 KB Output is correct
97 Correct 9 ms 1884 KB Output is correct
98 Correct 9 ms 1800 KB Output is correct
99 Correct 9 ms 1740 KB Output is correct
100 Correct 8 ms 1748 KB Output is correct
101 Correct 0 ms 212 KB Output is correct
102 Correct 0 ms 212 KB Output is correct
103 Correct 10 ms 1876 KB Output is correct
104 Correct 0 ms 212 KB Output is correct
105 Correct 1 ms 468 KB Output is correct
106 Correct 3 ms 596 KB Output is correct
107 Correct 1 ms 468 KB Output is correct
108 Correct 2 ms 468 KB Output is correct
109 Correct 5 ms 1108 KB Output is correct
110 Correct 5 ms 1108 KB Output is correct
111 Correct 9 ms 1876 KB Output is correct
112 Correct 0 ms 212 KB Output is correct
113 Correct 1 ms 212 KB Output is correct
114 Correct 9 ms 1788 KB Output is correct
115 Correct 1 ms 340 KB Output is correct
116 Correct 1 ms 428 KB Output is correct
117 Correct 5 ms 980 KB Output is correct
118 Correct 5 ms 1108 KB Output is correct
119 Correct 8 ms 1748 KB Output is correct
120 Correct 8 ms 1748 KB Output is correct
121 Correct 11 ms 1748 KB Output is correct
122 Correct 9 ms 1840 KB Output is correct
123 Correct 11 ms 1828 KB Output is correct
124 Correct 9 ms 1876 KB Output is correct
125 Correct 9 ms 1876 KB Output is correct
126 Correct 9 ms 1748 KB Output is correct
127 Correct 8 ms 1748 KB Output is correct
128 Correct 8 ms 1748 KB Output is correct