oj.uz

Submission #293289

# Submission time Handle Problem Language Result Execution time Memory
293289 2020-09-07T20:33:36 Z TheRedstar Vision Program (IOI19_vision) C++14
26 / 100
 48 ms 4472 KB 
#include "vision.h"

#include <bits/stdc++.h>


using namespace std;


typedef vector<int> vi;


int W,H,K;
int nMEM, nDIAG, nDIF, nBAND;

int memory(int x, int y) {return x+W*y;}
int diag1(int i) {return nMEM+i +1;}
int diag2(int i) {return diag1(nDIAG) +i;}
int dif1(int i) {return diag2(nDIAG) +i;}
int dif2(int i) {return dif1(nDIF) +i;}
int band1(int i) {return dif2(nDIF) +i;}
int band2(int i) {return band1(nBAND) +i;}



void construct_network(int h, int w, int k) {
	W=w;
	H=h;
	K=k;
	
	nMEM=W*H;
	nDIAG=W+H-1;
	nDIF=nDIAG-K;
	nBAND=nDIF;
	
	vi Ns;
	
	int always_false=add_xor({0,0});
	
	//cout << "diag1\n";
	//diag1
	int startx,starty;
	for(int i=0; i<nDIAG; i++) {
		Ns={};
		starty=H-1-i;
		startx=0-min(0,starty);
		starty=max(0,starty);
		for(int j=0; startx+j<W and starty+j<H; j++)
			Ns.push_back(memory(startx+j, starty+j));

		add_or(Ns);	
	}
	
	//cout << "diag2\n";
	//diag2
	for(int i=0; i<nDIAG; i++) {
		Ns={};
		starty=H-1-i;
		startx=W-1+min(0,starty);
		starty=max(0,starty);
		for(int j=0; startx-j>=0 and starty+j<H; j++)
			Ns.push_back(memory(startx-j, starty+j));

		add_or(Ns);	
	}
	
	//cout << "dif1\n";
	//dif1
	for(int i=0; i<nDIF; i++) {
		Ns={diag1(i),diag1(i+K)};
		add_and(Ns);	
	}
	
	//cout << "dif2\n";
	//dif2
	for(int i=0; i<nDIF; i++) {
		Ns={diag2(i),diag2(i+K)};
		add_and(Ns);	
	}
	
	//cout << "band1\n";
	//band1
	for(int i=0; i<nBAND; i++) {
		Ns={always_false};
		for(int j=-1; i+j>=0; j--) Ns.push_back(diag1(i+j));
		for(int j=K+1; i+j<nBAND; j++) Ns.push_back(diag1(i+j));
		add_or(Ns); // add not(and(band))
	}
	
	//cout << "band2\n";
	//band2
	for(int i=0; i<nBAND; i++) {
		Ns={always_false};
		for(int j=-1; i+j>=0; j--) Ns.push_back(diag2(i+j));
		for(int j=K+1; i+j<nBAND; j++) Ns.push_back(diag2(i+j));
		add_or(Ns); // add not(and(band))
	}
	
	//cout << "dif1 or\n";
	//or for dif1
	Ns={};
	for(int i=0; i<nDIF; i++) Ns.push_back(dif1(i));
	int or_dif1=add_or(Ns);
	
	//cout << "dif2 or\n";
	//or for dif2
	Ns={};
	for(int i=0; i<nDIF; i++) Ns.push_back(dif2(i));
	int or_dif2=add_or(Ns);
	
	//cout << "band1 or\n";
	//not and band1
	Ns={};
	for(int i=0; i<nBAND; i++) Ns.push_back(band1(i));
	int or_band1=add_not(add_and(Ns));
	
	//cout << "band2 or\n";
	//not and band1
	Ns={};
	for(int i=0; i<nBAND; i++) Ns.push_back(band2(i));
	int or_band2=add_not(add_and(Ns));
	
	//cout << "final\n";
	add_or({add_and({or_dif1,or_band2}), add_and({or_dif2,or_band1})});
	
}

Subtask #1
0 / 10.0

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

Subtask #2
0 / 11.0

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

Subtask #3
0 / 11.0

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

Subtask #4
0 / 15.0

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

Subtask #5
12.0 / 12.0

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

Subtask #6
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 256 KB Output is correct
2 Correct 0 ms 256 KB Output is correct
3 Correct 6 ms 768 KB Output is correct
4 Correct 3 ms 512 KB Output is correct
5 Correct 2 ms 504 KB Output is correct
6 Correct 1 ms 384 KB Output is correct
7 Correct 2 ms 384 KB Output is correct
8 Correct 10 ms 1024 KB Output is correct
9 Correct 5 ms 768 KB Output is correct
10 Correct 3 ms 512 KB Output is correct
11 Correct 2 ms 512 KB Output is correct
12 Correct 2 ms 512 KB Output is correct
13 Correct 10 ms 1024 KB Output is correct
14 Correct 4 ms 640 KB Output is correct
15 Correct 1 ms 384 KB Output is correct
16 Correct 1 ms 384 KB Output is correct
17 Correct 10 ms 1024 KB Output is correct
18 Correct 2 ms 512 KB Output is correct
19 Correct 1 ms 384 KB Output is correct
20 Correct 27 ms 2560 KB Output is correct
21 Incorrect 12 ms 1280 KB on inputs (0, 0), (199, 99), expected 0, but computed 1
22 Halted 0 ms 0 KB -

Subtask #7
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 48 ms 4344 KB Output is correct
2 Correct 1 ms 256 KB Output is correct
3 Correct 5 ms 768 KB Output is correct
4 Correct 10 ms 1024 KB Output is correct
5 Correct 10 ms 1024 KB Output is correct
6 Correct 10 ms 1024 KB Output is correct
7 Correct 27 ms 2552 KB Output is correct
8 Correct 27 ms 2552 KB Output is correct
9 Correct 48 ms 4472 KB Output is correct
10 Correct 1 ms 256 KB Output is correct
11 Correct 1 ms 256 KB Output is correct

Subtask #8
0 / 19.0

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