oj.uz

Submission #293190

# Submission time Handle Problem Language Result Execution time Memory
293190 2020-09-07T18:05:55 Z AlanChen Vision Program (IOI19_vision) C++14
47 / 100
 16 ms 2108 KB 
#include "vision.h"


#include <bits/stdc++.h>
using namespace std;

template<class A> using v=vector<A>;
template<class A,class B=A> using p=pair<A,B>;

typedef v<int> vi;
typedef p<int> pi;
typedef string str;

#define f first
#define s second
#define mp make_pair
#define ins insert
#define pb push_back
#define sz(S) (int)S.size()


#define get4(a,b,c,d,...) d

#define lp3(x,a,b) for(int x=(a);x<(b);x++)
#define lp2(x,a) lp3(x,0,a)
#define lp1(a) lp2(loopvar,a)
#define lp(x...) get4(x,lp3,lp2,lp1,0)(x)

#define trv(x,S) for(auto& x:(S))


int c0,c1;
struct num
{
	int x[8];
	num()
	{
		lp(i,8) x[i]=c0;
	}
};
num addnum(num n1,num n2)
{
	num ans;
	int carry=add_and({{n1.x[0],n2.x[0]}});
	ans.x[0]=add_xor({n1.x[0],n2.x[0]});
	lp(i,1,8){
		ans.x[i]=add_xor({carry,n1.x[i],n2.x[i]});
		if(i<7) carry=add_or({
			add_and({n1.x[i],n2.x[i]}),
					add_and({carry,n2.x[i]}),
					add_and({n1.x[i],carry})
		});
	}
	return ans;
}
num cplm(num n1)
{
	num ans;
	lp(i,8) ans.x[i]=add_not(n1.x[i]);

	num n2;
	n2.x[0]=c1;

	return addnum(ans,n2);
}

int n,m,tgt;
int orig[500][500];
int prj[2][500];
int disthelp[2][500][500];
int dist[2][500];
int isx[2][500];
int dim[2];




void construct_network(int H, int W, int Tgt)
{
	n=H,m=W,tgt=Tgt;


	{
		vi Ns;
		lp(i,n*m) {
			Ns.pb(i);
		}
		c1=add_or(Ns);
		c0=add_not(c1);
	}

	lp(i,n) lp(j,m) orig[i][j]=i*m+j;

	lp(i,n)
	{
		vi Ns;
		lp(j,m) Ns.pb(orig[i][j]);
		prj[0][i]=add_or(Ns);
	}
	lp(j,m)
	{
		vi Ns;
		lp(i,n) Ns.pb(orig[i][j]);
		prj[1][j]=add_or(Ns);
	}
	dim[0]=n,dim[1]=m;


	num fds[2];
	lp(d,2)
	{
		int iss;
		{
			vi Ns;
			lp(i,dim[d]) Ns.pb(prj[d][i]);
			iss=add_xor(Ns);
		}
		int isn=add_not(iss);


		int issamebit[7];
		int consenbit[7];
		lp(i,7)
		{
			vi Ns; Ns.pb(c0);
			lp(j,dim[d]) if(bitset<8>(j)[i]) Ns.pb(prj[d][j]);
			issamebit[i]=add_not(add_xor(Ns));
			consenbit[i]=add_or(Ns);
		}
		num possnums[8][2];
		lp(numsame,8)
		{
			lp(i,numsame) lp(j,2) possnums[numsame][j].x[i]=consenbit[i];
			lp(i,numsame,7) lp(j,2){
				vi Ns; Ns.pb(c0);
				lp(alln,dim[d]) if(bitset<8>(alln)[numsame]==j&&bitset<8>(alln)[i]) Ns.pb(prj[d][alln]);
				possnums[numsame][j].x[i]=add_or(Ns);
			}
		}
		num curr[2];
		lp(j,2) curr[j]=possnums[0][j];

		lp(i,1,7) issamebit[i]=add_and({issamebit[i-1],issamebit[i]});

		lp(j,2) lp(ns,1,8) lp(bt,7){
			curr[j].x[bt]=add_or({
				add_and({issamebit[ns-1],possnums[ns][j].x[bt]}),
						add_and({add_not(issamebit[ns-1]),curr[j].x[bt]})
			});
		}
		num diff=addnum(curr[0],cplm(curr[1]));
		num diff2=cplm(diff);
		num fd;
		lp(bt,8) fd.x[bt]=add_or({
			add_and({diff2.x[7],diff.x[bt]}),
					add_and({diff.x[7],diff2.x[bt]})
		});
		lp(bt,8) fd.x[bt]=add_and({isn,fd.x[bt]});
		fds[d]=fd;

	}
	num ttl=addnum(fds[0],fds[1]);

	vi ansarr;

	lp(i,8)
	{
		if(bitset<8>(tgt)[i]) ansarr.pb(ttl.x[i]);
		else ansarr.pb(add_not(ttl.x[i]));
	}

	add_and(ansarr);
}

Subtask #1
10.0 / 10.0

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

Subtask #2
11.0 / 11.0

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

Subtask #3
11.0 / 11.0

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

Subtask #4
15.0 / 15.0

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

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 512 KB on inputs (0, 1), (0, 128), expected 0, but computed 1
2 Halted 0 ms 0 KB -

Subtask #6
0 / 8.0

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

Subtask #7
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 2108 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 3 ms 768 KB Output is correct
4 Correct 5 ms 768 KB Output is correct
5 Incorrect 2 ms 508 KB on inputs (0, 1), (0, 128), expected 0, but computed 1
6 Halted 0 ms 0 KB -

Subtask #8
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 1 ms 512 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 1 ms 384 KB Output is correct
7 Correct 1 ms 384 KB Output is correct
8 Correct 1 ms 512 KB Output is correct
9 Correct 2 ms 512 KB Output is correct
10 Correct 1 ms 384 KB Output is correct
11 Correct 1 ms 384 KB Output is correct
12 Correct 1 ms 384 KB Output is correct
13 Correct 1 ms 512 KB Output is correct
14 Correct 1 ms 640 KB Output is correct
15 Correct 1 ms 512 KB Output is correct
16 Correct 1 ms 384 KB Output is correct
17 Correct 2 ms 384 KB Output is correct
18 Correct 1 ms 384 KB Output is correct
19 Correct 1 ms 384 KB Output is correct
20 Correct 1 ms 512 KB Output is correct
21 Correct 2 ms 512 KB Output is correct
22 Correct 1 ms 512 KB Output is correct
23 Correct 3 ms 512 KB Output is correct
24 Correct 1 ms 512 KB Output is correct
25 Correct 1 ms 512 KB Output is correct
26 Correct 1 ms 512 KB Output is correct
27 Correct 1 ms 512 KB Output is correct
28 Correct 2 ms 512 KB Output is correct
29 Correct 1 ms 384 KB Output is correct
30 Correct 1 ms 512 KB Output is correct
31 Correct 2 ms 512 KB Output is correct
32 Correct 2 ms 512 KB Output is correct
33 Correct 2 ms 512 KB Output is correct
34 Correct 2 ms 512 KB Output is correct
35 Correct 2 ms 512 KB Output is correct
36 Correct 2 ms 512 KB Output is correct
37 Correct 2 ms 512 KB Output is correct
38 Correct 5 ms 896 KB Output is correct
39 Correct 3 ms 512 KB Output is correct
40 Correct 2 ms 640 KB Output is correct
41 Correct 5 ms 768 KB Output is correct
42 Correct 4 ms 640 KB Output is correct
43 Correct 5 ms 896 KB Output is correct
44 Correct 6 ms 896 KB Output is correct
45 Correct 5 ms 1024 KB Output is correct
46 Correct 5 ms 896 KB Output is correct
47 Correct 5 ms 896 KB Output is correct
48 Incorrect 2 ms 512 KB on inputs (0, 1), (0, 128), expected 0, but computed 1
49 Halted 0 ms 0 KB -