Submission #246787

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
246787	2020-07-10T08:07:17 Z	Evirir	Vision Program (IOI19_vision)	C++17	12 / 100	40 ms	4084 KB

vision

#include "vision.h"
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;

#define watch(x) cout<<(#x)<<"="<<x<<endl
#define forn(i,a,b) for(int i=(a);i<(b);i++)
#define fore(i,a,b) for(int i=(a);i<=(b);i++)
#define pb push_back
#define F first
#define S second
#define fbo find_by_order
#define ook order_by_key
typedef long long ll;
typedef vector<int> vi;
typedef pair<ll,ll> ii;
typedef vector<ii> vii;
typedef long double ld;
typedef tree<ll, null_type, less<ll>, rb_tree_tag, tree_order_statistics_node_update> pbds;
void SD(int t=0){ cout<<"TEST "<<t<<endl; }

const int MAXN = 405;
const int MOD = 1e9+7;
bool DEBUG=0;
/*
int add_and(std::vector<int> Ns);
int add_or(std::vector<int> Ns);
int add_xor(std::vector<int> Ns);
int add_not(int N);
*/

int dist(ii a, ii b)
{
	return abs(a.F-b.F)+abs(a.S-b.S);
}

vi v;
int off;

vector<int> d1[MAXN],d2[MAXN];
int t1[2],t2[2];

void construct_network(int n, int m, int K)
{
	if(n*m==2){
		add_or({0,1});
		return;
	}
	
	off=m-1;
	vi all;
	
	for(int i=0;i<n;i++) for(int j=0;j<m;j++)
	{
		all.pb(i*m+j);
		d1[i+j].pb(i*m+j);
		d2[i-j+off].pb(i*m+j);
	}
	
	//create dummy 0 and 1
	int zero = add_and(all);
	int one = add_or(all);
	
	forn(i,0,m+n-1)
	{
		int tmp=add_or(d1[i]);
		if(i==0) t1[0]=tmp;
		if(i==m+n-2) t1[1]=tmp;
	}
	forn(i,0,m+n-1)
	{
		int tmp=add_or(d2[i]);
		if(i==0) t2[0]=tmp;
		if(i==m+n-2) t2[1]=tmp;
	}
	
	vi exact,test;
	
	//----------------------------------------------
	//d1 K, d2 large
	for(int i=t1[0];i+K<=t1[1];i++)
	{
		v={i,i+K};
		exact.pb(add_and(v)); if(DEBUG) cout<<"exact: "<<exact.back()<<endl;
	}
	for(int i=t2[0];i+K+1<=t2[1];i++)
	{
		v={i};
		for(int j=i+K+1;j<=t2[1];j++) v.pb(j);
		test.pb(add_and(v)); if(DEBUG) cout<<"test: "<<test.back()<<endl;
	}
	
	int f1,f2;
	int final1, final2;
	
	if(DEBUG){
		cout<<"exact.size()="<<exact.size()<<endl;
		cout<<"test.size()="<<test.size()<<endl;
	}
	
	f1 = (exact.size() ? add_or(exact) : zero);
	f2 = (test.size() ? add_not(add_or(test)) : one);
	
	v = {f1,f2}; if(DEBUG){ watch(f1); watch(f2); }
	final1=add_and(v);
	//phase 1 end
	//----------------------------------------------
	
	exact.clear(); test.clear(); v.clear();
	
	//----------------------------------------------
	//d2 exact, d1 large
	for(int i=t2[0];i+K<=t2[1];i++)
	{
		v={i,i+K};
		exact.pb(add_and(v)); if(DEBUG) cout<<"exact: "<<exact.back()<<endl;
	}
	for(int i=t1[0];i+K+1<=t1[1];i++)
	{
		v={i};
		for(int j=i+K+1;j<=t1[1];j++) v.pb(j);
		test.pb(add_and(v)); if(DEBUG) cout<<"test: "<<test.back()<<endl;
	}
	
	f1 = (exact.size() ? add_or(exact) : zero);
	f2 = (test.size() ? add_not(add_or(test)) : one);
	
	v = {f1,f2}; if(DEBUG){ watch(f1); watch(f2); }
	final2=add_and(v);
	//phase 2 end
	//----------------------------------------------
	
	//----------------------------------------------
	//check one of them is correct
	v = {final1, final2};
	add_or(v);
}

Subtask #1
0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	5 ms	384 KB	Output is correct
2	Correct	4 ms	384 KB	Output is correct
3	Correct	5 ms	384 KB	Output is correct
4	Correct	5 ms	384 KB	Output is correct
5	Correct	5 ms	384 KB	Output is correct
6	Correct	5 ms	384 KB	Output is correct
7	Incorrect	5 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	5 ms	384 KB	Output is correct
2	Correct	4 ms	384 KB	Output is correct
3	Correct	5 ms	384 KB	Output is correct
4	Correct	5 ms	384 KB	Output is correct
5	Correct	5 ms	384 KB	Output is correct
6	Correct	5 ms	384 KB	Output is correct
7	Incorrect	5 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	5 ms	384 KB	Output is correct
2	Correct	4 ms	384 KB	Output is correct
3	Correct	5 ms	384 KB	Output is correct
4	Correct	5 ms	384 KB	Output is correct
5	Correct	5 ms	384 KB	Output is correct
6	Correct	5 ms	384 KB	Output is correct
7	Incorrect	5 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	5 ms	384 KB	Output is correct
2	Correct	4 ms	384 KB	Output is correct
3	Correct	5 ms	384 KB	Output is correct
4	Correct	5 ms	384 KB	Output is correct
5	Correct	5 ms	384 KB	Output is correct
6	Correct	5 ms	384 KB	Output is correct
7	Incorrect	5 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	9 ms	768 KB	Output is correct
2	Correct	6 ms	512 KB	Output is correct
3	Correct	7 ms	640 KB	Output is correct
4	Correct	5 ms	384 KB	Output is correct
5	Correct	9 ms	768 KB	Output is correct
6	Correct	7 ms	512 KB	Output is correct
7	Correct	5 ms	384 KB	Output is correct
8	Correct	5 ms	384 KB	Output is correct
9	Correct	9 ms	768 KB	Output is correct
10	Correct	7 ms	640 KB	Output is correct
11	Correct	6 ms	512 KB	Output is correct
12	Correct	6 ms	512 KB	Output is correct
13	Correct	5 ms	384 KB	Output is correct
14	Correct	5 ms	384 KB	Output is correct
15	Correct	9 ms	768 KB	Output is correct
16	Correct	7 ms	640 KB	Output is correct
17	Correct	6 ms	512 KB	Output is correct
18	Correct	6 ms	512 KB	Output is correct
19	Correct	7 ms	384 KB	Output is correct
20	Correct	5 ms	384 KB	Output is correct
21	Correct	5 ms	384 KB	Output is correct
22	Correct	5 ms	384 KB	Output is correct

Subtask #6
0 / 8.0

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

Subtask #7
0 / 14.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	40 ms	4084 KB	on inputs (126, 120), (176, 169), expected 0, but computed 1
2	Halted	0 ms	0 KB	-

Subtask #8
0 / 19.0

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

Submission #246787

Compilation message