oj.uz

Submission #626083

# Submission time Handle Problem Language Result Execution time Memory
626083 2022-08-11T08:05:14 Z TimDee Vision Program (IOI19_vision) C++17
24 / 100
 11 ms 1428 KB 
#include "vision.h"
#include <bits/stdc++.h>
using namespace std;

void construct_network(int h, int w, int k) {

	if (h*w==2) {
		if (k==1) add_and({0,1});
		else add_xor({0,1});
		return;
	}

	int zero = add_and({0,1,2});
	int one = add_not(zero);

	vector<int> row(h,0);
	vector<int> col(w,0);

	for (int i=0; i<h; ++i) {
		vector<int> a;
		for (int j=0; j<w; ++j) {
			a.push_back(i*w+j);
		}
		row[i]=add_xor(a);
	}
	for (int j=0; j<w; ++j) {
		vector<int> a;
		for (int i=0; i<h; ++i) {
			a.push_back(i*w+j);
		}
		col[j]=add_xor(a);
	}
	int _check1 = add_or(row), _check2 = add_or(col);
	int check1 = add_not(_check1), check2 = add_not(_check2);
	vector<int> row_k={zero}, col_k={zero};
	for (int j=0; j+k<w; ++j) col_k.push_back(add_and({col[j],col[j+k]}));
	for (int i=0; i+k<h; ++i) row_k.push_back(add_and({row[i],row[i+k]}));

	int _a1=add_or(col_k), _a2=add_or(row_k);
	int inSameRow=add_and({check1,_a1}), inSameCol=add_and({check2,_a2});

	vector<int> prefRow, sufRow, prefCol, sufCol;
	prefRow={row[0]};
	for (int i=1; i<h; ++i) {
		prefRow.push_back(add_xor({row[i],prefRow[i-1]}));
	}
	sufRow={row[h-1]};
	for (int i=h-2; i>=0; --i) {
		sufRow.push_back(add_xor({row[i],sufRow[h-2-i]}));
	}
	prefCol={col[0]};
	for (int i=1; i<w; ++i) {
		prefCol.push_back(add_xor({col[i],prefCol[i-1]}));
	}
	sufCol={col[w-1]};
	for (int i=w-2; i>=0; --i) {
		sufCol.push_back(add_xor({col[i],sufCol[w-2-i]}));
	}

	vector<int> bitxl, bityl, bitxr, bityr;
	vector<int> rl(h), cl(w), rr(h), cr(w);

	for (int i=0; i<h; ++i) {
		//cout<<"PrefRow\n";
		int p=add_and({i?prefRow[i-1]:zero,(i<(h-1))?prefRow[i+1]:zero});
		int q=add_xor({p,prefRow[i],i?prefRow[i-1]:zero});
		rl[i]=add_and({q,prefRow[i]});
	}
	for (int i=0; i<h; ++i) {
		//cout<<"SufRow\n";
		int p=add_and({i?sufRow[i-1]:zero,(i<(h-1))?sufRow[i+1]:zero});
		int q=add_xor({p,sufRow[i],i?sufRow[i-1]:zero});
		rr[h-1-i]=add_and({q,sufRow[i]});
	}
	for (int i=0; i<w; ++i) {
		//cout<<"PrefCol\n";
		int p=add_and({i?prefCol[i-1]:zero,(i<(w-1))?prefCol[i+1]:zero});
		int q=add_xor({p,prefCol[i],i?prefCol[i-1]:zero});
		cl[i]=add_and({q,prefCol[i]});
	}
	for (int i=0; i<w; ++i) {
		//cout<<"SufCol\n";
		int p=add_and({i?sufCol[i-1]:zero,(i<(w-1))?sufCol[i+1]:zero});
		int q=add_xor({p,sufCol[i],i?sufCol[i-1]:zero});
		cr[w-1-i]=add_and({q,sufCol[i]});
	}

	for (int i=0; (1<<i)<h; ++i) {
		vector<int> a;
		for (int x=0; x<h; ++x) {
			if (x & (1<<i)) a.push_back(rl[x]);
		}
		bitxl.push_back(add_or(a));
	}
	for (int i=0; (1<<i)<w; ++i) {
		vector<int> a;
		for (int x=0; x<w; ++x) {
			if (x & (1<<i)) a.push_back(cl[x]);
		}
		bityl.push_back(add_or(a));
	}
	for (int i=0; (1<<i)<h; ++i) {
		vector<int> a;
		for (int x=0; x<h; ++x) {
			if (x & (1<<i)) a.push_back(rr[x]);
		}
		bitxr.push_back(add_or(a));
	}
	for (int i=0; (1<<i)<w; ++i) {
		vector<int> a;
		for (int x=0; x<w; ++x) {
			if (x & (1<<i)) a.push_back(cr[x]);
		}
		bityr.push_back(add_or(a));
	}

	vector<int> xorx(10,zero),xory(10,zero),ansbitx(10,zero),ansbity(10,zero),ansbit(10,zero);
	for (int i=0; (1<<i)<h; ++i) {
		xorx[i]=add_xor({bitxl[i],bitxr[i]});
	}
	for (int i=0; (1<<i)<w; ++i) {
		xory[i]=add_xor({bityl[i],bityr[i]});
	}
	ansbitx[0]=xorx[0];
	ansbity[0]=xory[0];
	for (int i=1; (1<<i)<h; ++i) {
		int p=add_and({xorx[i-1],bitxl[i-1]});
		ansbitx[i]=add_xor({xorx[i],p});
	}
	for (int i=1; (1<<i)<w; ++i) {
		int q=add_and({xory[i-1],bityl[i-1]});
		ansbity[i]=add_xor({xory[i],q});
	}

	vector<int> xorans(10,zero);
	for (int i=0; i<10; ++i) xorans[i]=add_xor({ansbity[i],ansbitx[i]});

	ansbit[0]=xorans[0];
	for (int i=1; i<10; ++i) {
		int p=add_and({ansbitx[i-1],ansbity[i-1]});
		int q=add_or({ansbitx[i-1],ansbity[i-1]});
		int t=add_xor({q,ansbit[i-1]});
		int z=add_and({t,q});
		int o=add_or({p,z});
		ansbit[i]=add_xor({xorans[i],o});
	}	

	vector<int> forans;
	for (int i=0; i<10; ++i) {

		if (k&(1<<i)) forans.push_back(ansbit[i]);
		else {
			int v=add_not(ansbit[i]);
			forans.push_back(v);
		}

	}
	int ans=add_and(forans);
	add_or({ans,inSameCol,inSameRow});

}

Compilation message

vision.cpp: In function 'void construct_network(int, int, int)':
vision.cpp:14:6: warning: unused variable 'one' [-Wunused-variable]
   14 |  int one = add_not(zero);
      |      ^~~

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 1 ms 212 KB Output is correct
4 Correct 1 ms 300 KB Output is correct
5 Correct 1 ms 296 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 0 ms 296 KB Output is correct
9 Correct 1 ms 300 KB Output is correct
10 Correct 1 ms 300 KB Output is correct
11 Correct 1 ms 212 KB Output is correct
12 Correct 1 ms 296 KB Output is correct
13 Correct 1 ms 256 KB Output is correct
14 Correct 1 ms 296 KB Output is correct
15 Correct 1 ms 320 KB Output is correct
16 Correct 1 ms 300 KB Output is correct
17 Correct 1 ms 296 KB Output is correct
18 Correct 0 ms 296 KB Output is correct

Subtask #2
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 1 ms 212 KB Output is correct
4 Correct 1 ms 300 KB Output is correct
5 Correct 1 ms 296 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 0 ms 296 KB Output is correct
9 Correct 1 ms 300 KB Output is correct
10 Correct 1 ms 300 KB Output is correct
11 Correct 1 ms 212 KB Output is correct
12 Correct 1 ms 296 KB Output is correct
13 Correct 1 ms 256 KB Output is correct
14 Correct 1 ms 296 KB Output is correct
15 Correct 1 ms 320 KB Output is correct
16 Correct 1 ms 300 KB Output is correct
17 Correct 1 ms 296 KB Output is correct
18 Correct 0 ms 296 KB Output is correct
19 Correct 0 ms 340 KB Output is correct
20 Correct 1 ms 300 KB Output is correct
21 Incorrect 1 ms 212 KB on inputs (0, 0), (0, 3), expected 0, but computed 1
22 Halted 0 ms 0 KB -

Subtask #3
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 1 ms 212 KB Output is correct
4 Correct 1 ms 300 KB Output is correct
5 Correct 1 ms 296 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 0 ms 296 KB Output is correct
9 Correct 1 ms 300 KB Output is correct
10 Correct 1 ms 300 KB Output is correct
11 Correct 1 ms 212 KB Output is correct
12 Correct 1 ms 296 KB Output is correct
13 Correct 1 ms 256 KB Output is correct
14 Correct 1 ms 296 KB Output is correct
15 Correct 1 ms 320 KB Output is correct
16 Correct 1 ms 300 KB Output is correct
17 Correct 1 ms 296 KB Output is correct
18 Correct 0 ms 296 KB Output is correct
19 Correct 0 ms 340 KB Output is correct
20 Correct 1 ms 300 KB Output is correct
21 Incorrect 1 ms 212 KB on inputs (0, 0), (0, 3), expected 0, but computed 1
22 Halted 0 ms 0 KB -

Subtask #4
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 1 ms 212 KB Output is correct
4 Correct 1 ms 300 KB Output is correct
5 Correct 1 ms 296 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 0 ms 296 KB Output is correct
9 Correct 1 ms 300 KB Output is correct
10 Correct 1 ms 300 KB Output is correct
11 Correct 1 ms 212 KB Output is correct
12 Correct 1 ms 296 KB Output is correct
13 Correct 1 ms 256 KB Output is correct
14 Correct 1 ms 296 KB Output is correct
15 Correct 1 ms 320 KB Output is correct
16 Correct 1 ms 300 KB Output is correct
17 Correct 1 ms 296 KB Output is correct
18 Correct 0 ms 296 KB Output is correct
19 Correct 0 ms 340 KB Output is correct
20 Correct 1 ms 300 KB Output is correct
21 Incorrect 1 ms 212 KB on inputs (0, 0), (0, 3), expected 0, but computed 1
22 Halted 0 ms 0 KB -

Subtask #5
0 / 12.0

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

Subtask #6
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 2 ms 468 KB Output is correct
4 Incorrect 2 ms 468 KB on inputs (0, 0), (3, 28), expected 1, but computed 0
5 Halted 0 ms 0 KB -

Subtask #7
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 1360 KB Output is correct
2 Correct 1 ms 296 KB Output is correct
3 Correct 2 ms 468 KB Output is correct
4 Correct 4 ms 468 KB Output is correct
5 Correct 2 ms 468 KB Output is correct
6 Correct 2 ms 552 KB Output is correct
7 Correct 6 ms 980 KB Output is correct
8 Correct 6 ms 980 KB Output is correct
9 Correct 11 ms 1428 KB Output is correct
10 Correct 0 ms 212 KB Output is correct
11 Correct 0 ms 296 KB Output is correct

Subtask #8
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 1 ms 212 KB Output is correct
4 Correct 1 ms 300 KB Output is correct
5 Correct 1 ms 296 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 0 ms 296 KB Output is correct
9 Correct 1 ms 300 KB Output is correct
10 Correct 1 ms 300 KB Output is correct
11 Correct 1 ms 212 KB Output is correct
12 Correct 1 ms 296 KB Output is correct
13 Correct 1 ms 256 KB Output is correct
14 Correct 1 ms 296 KB Output is correct
15 Correct 1 ms 320 KB Output is correct
16 Correct 1 ms 300 KB Output is correct
17 Correct 1 ms 296 KB Output is correct
18 Correct 0 ms 296 KB Output is correct
19 Correct 0 ms 340 KB Output is correct
20 Correct 1 ms 300 KB Output is correct
21 Incorrect 1 ms 212 KB on inputs (0, 0), (0, 3), expected 0, but computed 1
22 Halted 0 ms 0 KB -