oj.uz

답안 #423540

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
423540 2021-06-11T09:04:42 Z errorgorn Vision Program (IOI19_vision) C++17
0 / 100
 11 ms 1704 KB 
//雪花飄飄北風嘯嘯
//天地一片蒼茫

#include "vision.h"

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/rope>
using namespace std;
using namespace __gnu_pbds;
using namespace __gnu_cxx;
#define ll long long
#define ii pair<ll,ll>
#define iii pair<ii,ll>
#define fi first
#define se second
#define endl '\n'
#define debug(x) cout << #x << ": " << x << endl

#define pub push_back
#define pob pop_back
#define puf push_front
#define pof pop_front
#define lb lower_bound
#define ub upper_bound

#define rep(x,start,end) for(auto x=(start)-((start)>(end));x!=(end)-((start)>(end));((start)<(end)?x++:x--))
#define all(x) (x).begin(),(x).end()
#define sz(x) (int)(x).size()

#define indexed_set tree<ll,null_type,less<ll>,rb_tree_tag,tree_order_statistics_node_update>
//change less to less_equal for non distinct pbds, but erase will bug

mt19937 rng(chrono::system_clock::now().time_since_epoch().count());

int h,w,k;
int IDX;

int TRUE_IDX; //creating a true

int row[205]; //store entire row
int col[205]; //store entire col

int rowb[10][2]; //(is there,not there)
int colb[10][2];

int rdist[205];
int cdist[205];

void construct_network(int H, int W, int K) {
	h=H,w=W,k=K;
	IDX=h*w;
	
	vector<int> vtrue;
	rep(x,0,h*w) vtrue.pub(x);
	add_or(vtrue);
	TRUE_IDX=IDX++;
	
	rep(x,0,h){
		vector<int> v;
		rep(y,0,w) v.pub(x*w+y);
		add_or(v);
		row[x]=IDX++;
	}
	
	rep(y,0,w){
		vector<int> v;
		rep(x,0,h) v.pub(x*w+y);
		add_or(v);
		col[y]=IDX++;
	}
	
	for (int p2=1;p2<=256;p2<<=1){
		vector<int> res;
		rep(x,0,h){
			vector<int> blacks;
			
			rep(y,x+1,h) if ((y-x)/p2%2==1){
				blacks.pub(row[y]);
			}
			
			if (blacks.empty()) break;
			
			add_or(blacks);
			add_and({row[x],IDX});
			res.pub(IDX+1);
			IDX+=2;
		}
		
		if (res.empty()) break;
		
		add_or(res);
		rowb[__builtin_ctz(p2)][0]=IDX;
		
		add_not(IDX);
		rowb[__builtin_ctz(p2)][1]=IDX+1;
		
		IDX+=2;
	}
	
	for (int p2=1;p2<=256;p2<<=1){
		vector<int> res;
		rep(x,0,w){
			vector<int> blacks;
			
			rep(y,x+1,w) if ((y-x)/p2%2==1){
				blacks.pub(col[y]);
			}
			
			if (blacks.empty()) break;
			
			add_or(blacks);
			add_and({col[x],IDX});
			res.pub(IDX+1);
			IDX+=2;
		}
		
		if (res.empty()) break;
		
		add_or(res);
		colb[__builtin_ctz(p2)][0]=IDX;
		
		add_not(IDX);
		colb[__builtin_ctz(p2)][1]=IDX+1;
		
		IDX+=2;
	}
	
	rep(x,0,h){
		vector<int> v;
		for (int p2=1;p2<h;p2<<=1){
			if (x&p2) v.pub(rowb[__builtin_ctz(p2)][0]);
			else v.pub(rowb[__builtin_ctz(p2)][1]);
		}
		
		if (v.empty()){
			rdist[x]=TRUE_IDX;
		}
		else{
			add_and(v);
			rdist[x]=IDX++;
		}
	}
	
	rep(x,0,w){
		vector<int> v;
		for (int p2=1;p2<w;p2<<=1){
			if (x&p2) v.pub(colb[__builtin_ctz(p2)][0]);
			else v.pub(colb[__builtin_ctz(p2)][1]);
		}
		
		if (v.empty()){
			cdist[x]=TRUE_IDX;
		}
		else{
			add_and(v);
			cdist[x]=IDX++;
		}
	}
	
	vector<int> v;
	rep(x,0,h){
		int y=k-x;
		if (y<w){
			add_and({rdist[x],cdist[y]});
			v.pub(IDX);
			IDX++;
		}
	}
	
	add_or(v);
}

Subtask #1
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Incorrect 1 ms 204 KB on inputs (0, 0), (2, 0), expected 0, but computed 1
4 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Incorrect 1 ms 204 KB on inputs (0, 0), (2, 0), expected 0, but computed 1
4 Halted 0 ms 0 KB -

Subtask #3
0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Incorrect 1 ms 204 KB on inputs (0, 0), (2, 0), expected 0, but computed 1
4 Halted 0 ms 0 KB -

Subtask #4
0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Incorrect 1 ms 204 KB on inputs (0, 0), (2, 0), expected 0, but computed 1
4 Halted 0 ms 0 KB -

Subtask #5
0 / 12.0

# 결과 실행 시간 메모리 Grader output
1 Correct 10 ms 968 KB Output is correct
2 Correct 11 ms 988 KB Output is correct
3 Correct 10 ms 972 KB Output is correct
4 Correct 10 ms 1028 KB Output is correct
5 Incorrect 2 ms 684 KB WA in grader: Invalid index
6 Halted 0 ms 0 KB -

Subtask #6
0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Incorrect 2 ms 460 KB WA in grader: Invalid index
4 Halted 0 ms 0 KB -

Subtask #7
0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 5 ms 1704 KB WA in grader: Invalid index
2 Halted 0 ms 0 KB -

Subtask #8
0 / 19.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Incorrect 1 ms 204 KB on inputs (0, 0), (2, 0), expected 0, but computed 1
4 Halted 0 ms 0 KB -