Submission #385576

#	Time	Username	Problem	Language	Result	Execution time	Memory
385576		Sprdalo	Vision Program (IOI19_vision)	C++17	100 / 100	106 ms	7528 KiB

vision

#include"vision.h"
#include<bits/stdc++.h>
using namespace std;
int solve(int h, int w, int k){
	vector<int>diagL[400], diagR[400], prefL, prefR, ans;
	for(int i=0; i<h; i++)
		for(int j=0; j<w; j++){
			diagL[i+j].push_back(i*w+j);
			diagR[i+(w-1-j)].push_back(i*w+j);
		}
	for(int d=k; d<h+w-1; d++){
		prefL.push_back(add_or(diagL[d-k]));
		prefR.push_back(add_or(diagR[d-k]));
		ans.push_back(add_and({add_or(diagL[d]), add_or(prefL)}));
		ans.push_back(add_and({add_or(diagR[d]), add_or(prefR)}));
	}
	return add_or(ans);
}
void construct_network(int h, int w, int k){
	if(k==h+w-2) solve(h, w, k);
	else add_and({solve(h, w, k), add_not(solve(h, w, k+1))});
}

/*
signed main()
{
    ios_base::sync_with_stdio(false); 
    cin.tie(nullptr); 
    cout.tie(nullptr); 
    cerr.tie(nullptr);    
    
    int h, w, k;
    cin >> h >> w >> k;

    int q; cin >> q;

    int x1=0, y1=0, x2=0, y2=0;
    for (int e = 0; e < q; ++e){
        A = vi(h*w,0);
        cin >> x1 >> y1 >> x2 >> y2;
        A[x1*w+y1] = A[x2*w+y2] = 1;

        last = -1;
        construct_network(h,w,k);

        cout << last << '\n';
    }
}signed main()
{
    ios_base::sync_with_stdio(false); 
    cin.tie(nullptr); 
    cout.tie(nullptr); 
    cerr.tie(nullptr);    
    
    int h, w, k;
    cin >> h >> w >> k;

    int q; cin >> q;

    int x1=0, y1=0, x2=0, y2=0;
    for (int e = 0; e < q; ++e){
        A = vi(h*w,0);
        cin >> x1 >> y1 >> x2 >> y2;
        A[x1*w+y1] = A[x2*w+y2] = 1;

        last = -1;
        construct_network(h,w,k);

        cout << last << '\n';
    }
}signed main()
{
    ios_base::sync_with_stdio(false); 
    cin.tie(nullptr); 
    cout.tie(nullptr); 
    cerr.tie(nullptr);    
    
    int h, w, k;
    cin >> h >> w >> k;

    int q; cin >> q;

    int x1=0, y1=0, x2=0, y2=0;
    for (int e = 0; e < q; ++e){
        A = vi(h*w,0);
        cin >> x1 >> y1 >> x2 >> y2;
        A[x1*w+y1] = A[x2*w+y2] = 1;

        last = -1;
        construct_network(h,w,k);

        cout << last << '\n';
    }
}signed main()
{
    ios_base::sync_with_stdio(false); 
    cin.tie(nullptr); 
    cout.tie(nullptr); 
    cerr.tie(nullptr);    
    
    int h, w, k;
    cin >> h >> w >> k;

    int q; cin >> q;

    int x1=0, y1=0, x2=0, y2=0;
    for (int e = 0; e < q; ++e){
        A = vi(h*w,0);
        cin >> x1 >> y1 >> x2 >> y2;
        A[x1*w+y1] = A[x2*w+y2] = 1;

        last = -1;
        construct_network(h,w,k);

        cout << last << '\n';
    }
}
*/

• Subtask 1: 10 / 10
• Subtask 2: 11 / 11
• Subtask 3: 11 / 11
• Subtask 4: 15 / 15
• Subtask 5: 12 / 12
• Subtask 6: 8 / 8
• Subtask 7: 14 / 14
• Subtask 8: 19 / 19