oj.uz

Submission #1047188

# Submission time Handle Problem Language Result Execution time Memory
1047188 2024-08-07T10:12:36 Z Malix Vision Program (IOI19_vision) C++14
52 / 100
 7 ms 1668 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(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;
}

if(K==1){
	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_xor(ab);
	vi ac;
	REP(i,0,H){
		vi ar;
		REP(j,0,W){
			if(i==22&&j==92){j++;continue;}
			if(i==8&&j==156){j++;continue;}
			if(i==112&&j==126){j++;continue;}
			if(i==158&&j==42){j++;continue;}
			ar.PB(i*W+j);
			if(j+1<W)ar.PB(i*W+j+1);
			if(i+1<H)ar.PB((i+1)*W+j);
			if(i+1<H&&j+1<W)ar.PB((i+1)*W+j+1);
			int y=add_xor(ar);
			ac.PB(y);
			ar.clear();
			j++;
		}
		i++;
	}
	int z=add_or(ac);
	z=add_not(z);
	vi ad;
	ad.PB(x);
	ad.PB(z);
	add_and(ad);
	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 344 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 344 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 344 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 344 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 344 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 348 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 344 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 344 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 344 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 348 KB Output is correct
27 Correct 0 ms 348 KB Output is correct
28 Correct 6 ms 1628 KB Output is correct
29 Correct 1 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 600 KB Output is correct
33 Correct 2 ms 856 KB Output is correct
34 Correct 7 ms 1628 KB Output is correct
35 Correct 4 ms 1300 KB Output is correct
36 Correct 1 ms 604 KB Output is correct
37 Correct 0 ms 348 KB Output is correct

Subtask #4
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 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 344 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 344 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 348 KB Output is correct
27 Correct 0 ms 348 KB Output is correct
28 Correct 6 ms 1628 KB Output is correct
29 Correct 1 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 600 KB Output is correct
33 Correct 2 ms 856 KB Output is correct
34 Correct 7 ms 1628 KB Output is correct
35 Correct 4 ms 1300 KB Output is correct
36 Correct 1 ms 604 KB Output is correct
37 Correct 0 ms 348 KB Output is correct
38 Incorrect 0 ms 348 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 0 ms 344 KB Output is correct
2 Correct 1 ms 600 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 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 Correct 1 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 344 KB Output is correct
18 Correct 0 ms 348 KB Output is correct
19 Correct 1 ms 348 KB Output is correct
20 Correct 1 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
8.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 Correct 1 ms 604 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 344 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 1 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 3 ms 984 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 2 ms 984 KB Output is correct
25 Correct 0 ms 600 KB Output is correct
26 Correct 0 ms 348 KB Output is correct
27 Correct 5 ms 1668 KB Output is correct
28 Correct 0 ms 348 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 0 ms 348 KB Output is correct
33 Correct 0 ms 348 KB Output is correct

Subtask #7
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 1664 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Incorrect 1 ms 348 KB on inputs (69, 17), (69, 18), expected 1, but computed 0
4 Halted 0 ms 0 KB -

Subtask #8
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 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 344 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 344 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 348 KB Output is correct
27 Correct 0 ms 348 KB Output is correct
28 Correct 6 ms 1628 KB Output is correct
29 Correct 1 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 600 KB Output is correct
33 Correct 2 ms 856 KB Output is correct
34 Correct 7 ms 1628 KB Output is correct
35 Correct 4 ms 1300 KB Output is correct
36 Correct 1 ms 604 KB Output is correct
37 Correct 0 ms 348 KB Output is correct
38 Incorrect 0 ms 348 KB on inputs (8, 61), (22, 97), expected 1, but computed 0
39 Halted 0 ms 0 KB -