oj.uz

Submission #1046983

# Submission time Handle Problem Language Result Execution time Memory
1046983 2024-08-07T07:19:36 Z Malix Vision Program (IOI19_vision) C++14
58 / 100
 6 ms 1708 KB 
#include "vision.h"
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vii;
typedef pair<int,int> pi;
typedef vector<pi> pii;
typedef tuple<int,int,int> tii;

#define REP(i,a,b) for(int i=a;i<b;i++)
#define F first
#define S second
#define PB push_back
#define MP make_pair
#define LSOne(s) ((s)&(-s))

ll INF=1e18+10;
int inf=1e9+10;
ll M=1e9+7;

void construct_network(int H, int W, int K) {
if(min(H,W)==1||H*W<=100){
	set<pi> a;
	REP(i,0,H){
		REP(j,0,W){
			int x=W*i+j;
			REP(k,0,K+1){
				int y=W*(i+k)+j+(K-k);
				if(i+k<H&&i+k>=0&&j+K-k>=0&&j+K-k<W&&y<H*W&&y>=0){
					if(x<y)a.insert({x,y});
					else a.insert({y,x});
				}
				y=W*(i-k)+j+(K-k);
				if(i-k<H&&i-k>=0&&j+K-k>=0&&j+K-k<W&&y<H*W&&y>=0){
					if(x<y)a.insert({x,y});
					else a.insert({y,x});
				}
				y=W*(i+k)+j-(K-k);
				if(i+k<H&&i+k>=0&&j-(K-k)>=0&&j-(K-k)<W&&y<H*W&&y>=0){
					if(x<y)a.insert({x,y});
					else a.insert({y,x});
				}
				y=W*(i-k)+j-(K-k);
				if(i-k<H&&i-k>=0&&j-(K-k)>=0&&j-(K-k)<W&&y<H*W&&y>=0){
					if(x<y)a.insert({x,y});
					else a.insert({y,x});
				}
			}
		}
	}
 
	vi b,c;
	for(auto u:a){
		b.clear();
		b.PB(u.F);
		b.PB(u.S);
		int x=add_and(b);
		c.PB(x);
	}
	if(c.empty()){
		int x=add_not(0);
		c.PB(x);c.PB(0);
		add_and(c);
	}
	else add_or(c);
	return;
}
if(K==1){
	vi c;
	REP(i,0,H){	
		vi b;
		vi a;
		REP(j,0,W){
			a.PB(i*W+j);
			j++;
		}
		int x=add_or(a);
		b.PB(x);
		a.clear();
		REP(j,1,W){
			a.PB(i*W+j);
			j++;
		}
		x=add_or(a);
		b.PB(x);
		int y=add_and(b);
		c.PB(y);
	}
	REP(i,0,W){
		vi b;
		vi a;
		REP(j,0,H){
			a.PB(j*W+i);
			j++;
		}
		int x=add_or(a);
		b.PB(x);
		a.clear();
		REP(j,1,H){
			a.PB(j*W+i);
			j++;
		}
		x=add_or(a);
		b.PB(x);
		int y=add_and(b);
		c.PB(y);
	}
	add_or(c);
	return;
}
if(H*W<=900){
	vi ab;
	REP(i,0,H){
		REP(j,0,W){
			ab.PB(i*W+j);
			j++;
		}
		i++;
		if(i>=H)continue;
		REP(j,1,W){
			ab.PB(i*W+j);
			j++;
		}
	}
	int x=add_or(ab);
	ab.clear();
	REP(i,0,H){
		REP(j,1,W){
			ab.PB(i*W+j);
			j++;
		}
		i++;
		if(i>=H)continue;
		REP(j,0,W){
			ab.PB(i*W+j);
			j++;
		}
	}
	int y=add_or(ab);
	ab.clear();
	ab.PB(x);ab.PB(y);
	int z=add_xor(ab);
	set<pi> a;
	REP(i,0,H){
		REP(j,0,W){
			int x=W*i+j;
			REP(k,0,K+1){
				int y=W*(i+k)+j+(K-k);
				if(i+k<H&&i+k>=0&&j+K-k>=0&&j+K-k<W&&y<H*W&&y>=0){
					if(x<y)a.insert({x,y});
					else a.insert({y,x});
				}
				y=W*(i-k)+j+(K-k);
				if(i-k<H&&i-k>=0&&j+K-k>=0&&j+K-k<W&&y<H*W&&y>=0){
					if(x<y)a.insert({x,y});
					else a.insert({y,x});
				}
				y=W*(i+k)+j-(K-k);
				if(i+k<H&&i+k>=0&&j-(K-k)>=0&&j-(K-k)<W&&y<H*W&&y>=0){
					if(x<y)a.insert({x,y});
					else a.insert({y,x});
				}
				y=W*(i-k)+j-(K-k);
				if(i-k<H&&i-k>=0&&j-(K-k)>=0&&j-(K-k)<W&&y<H*W&&y>=0){
					if(x<y)a.insert({x,y});
					else a.insert({y,x});
				}
			}
		}
	}
	vii arr(H*W+1);
	for(auto u:a){
		arr[u.F].PB(u.S);
	}
	vi brr;
	int count=0;
	REP(i,0,H*W+1){
		if(arr[i].empty())continue;
		vi crr;
		crr.PB(i);
		for(auto u:arr[i])crr.PB(u);
		if(count>9990)cerr<<i<<" ";
		int p=add_xor(crr);
		int r=add_or(crr);
		int q=add_not(p);
		vi drr;
		drr.PB(r);drr.PB(q);
		int v=add_and(drr);
		brr.PB(v);count+=4;
		
	}
	int t=add_or(brr);
	vi g;g.PB(t);
	if(K%2==0){
		g.PB(z);
		add_and(g);
	}
	else{
		int zz=add_not(z);
		g.PB(zz);
		add_and(g);
	}
	return;
}
	set<pi> a;
	int i=0,j=0;
	int x=W*i+j;
			REP(k,0,K+1){
				int y=W*(i+k)+j+(K-k);
				if(i+k<H&&i+k>=0&&j+K-k>=0&&j+K-k<W&&y<H*W&&y>=0){
					if(x<y)a.insert({x,y});
					else a.insert({y,x});
				}
				y=W*(i-k)+j+(K-k);
				if(i-k<H&&i-k>=0&&j+K-k>=0&&j+K-k<W&&y<H*W&&y>=0){
					if(x<y)a.insert({x,y});
					else a.insert({y,x});
				}
				y=W*(i+k)+j-(K-k);
				if(i+k<H&&i+k>=0&&j-(K-k)>=0&&j-(K-k)<W&&y<H*W&&y>=0){
					if(x<y)a.insert({x,y});
					else a.insert({y,x});
				}
				y=W*(i-k)+j-(K-k);
				if(i-k<H&&i-k>=0&&j-(K-k)>=0&&j-(K-k)<W&&y<H*W&&y>=0){
					if(x<y)a.insert({x,y});
					else a.insert({y,x});
				}
			}
			vi b,c;
	for(auto u:a){
		b.clear();
		b.PB(u.F);
		b.PB(u.S);
		int x=add_and(b);
		c.PB(x);
	}
	if(c.empty()){
		int x=add_not(0);
		c.PB(x);c.PB(0);
		add_and(c);
	}
	else add_or(c);
}

Subtask #1
10.0 / 10.0

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

Subtask #2
11.0 / 11.0

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

Subtask #3
11.0 / 11.0

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

Subtask #4
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 344 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Correct 0 ms 348 KB Output is correct
18 Correct 0 ms 348 KB Output is correct
19 Correct 0 ms 348 KB Output is correct
20 Correct 0 ms 348 KB Output is correct
21 Correct 0 ms 348 KB Output is correct
22 Correct 0 ms 348 KB Output is correct
23 Correct 0 ms 348 KB Output is correct
24 Correct 1 ms 348 KB Output is correct
25 Correct 0 ms 348 KB Output is correct
26 Correct 0 ms 344 KB Output is correct
27 Correct 0 ms 348 KB Output is correct
28 Correct 6 ms 1628 KB Output is correct
29 Correct 0 ms 348 KB Output is correct
30 Correct 0 ms 348 KB Output is correct
31 Correct 0 ms 348 KB Output is correct
32 Correct 1 ms 604 KB Output is correct
33 Correct 0 ms 348 KB Output is correct
34 Correct 5 ms 1708 KB Output is correct
35 Correct 4 ms 1372 KB Output is correct
36 Correct 1 ms 604 KB Output is correct
37 Correct 1 ms 348 KB Output is correct
38 Incorrect 1 ms 344 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 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 412 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct
13 Correct 0 ms 348 KB Output is correct
14 Correct 0 ms 348 KB Output is correct
15 Correct 0 ms 348 KB Output is correct
16 Correct 0 ms 348 KB Output is correct
17 Correct 0 ms 348 KB Output is correct
18 Correct 0 ms 348 KB Output is correct
19 Correct 1 ms 348 KB Output is correct
20 Correct 0 ms 348 KB Output is correct
21 Correct 0 ms 348 KB Output is correct
22 Correct 0 ms 348 KB Output is correct

Subtask #6
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Incorrect 1 ms 348 KB on inputs (0, 0), (43, 0), expected 0, but computed 1
9 Halted 0 ms 0 KB -

Subtask #7
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 1116 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1 ms 344 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 2 ms 860 KB Output is correct
8 Correct 2 ms 860 KB Output is correct
9 Correct 4 ms 1112 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct

Subtask #8
0 / 19.0

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