제출 #336504

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
336504		aryan12	Vision Program (IOI19_vision)	C++17	0 / 100	4 ms	1864 KiB

vision

#include "vision.h"
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5;
int a[N];

void MakeItGood(int h, int w) {
    for(int i = 0; i < h * w; i++) {
        a[i] = 0;
    }
}

/*int add_and(vector<int> x) {
    int ans = 1;
    cout << "And" << endl;
    for(int i = 0; i < x.size(); i++) {
        cout << x[i] << " ";
        ans &= a[x[i]];
    }
    cout << endl << "ans = " << ans << endl;
    return ans;
}

int add_or(vector<int> x) {
    int ans = 0;
    cout << "OR" << endl;
    for(int i = 0; i < x.size(); i++) {
        ans |= a[x[i]];
        cout << x[i] << " ";
    }
    cout << endl << "ans = " << ans << endl;
    return ans;
}

int add_xor(vector<int> x) {
    int ans = 0;
    cout << "XOR" << endl;
    for(int i = 0; i < x.size(); i++) {
        cout << x[i] << " ";
        ans ^= a[x[i]];
    }
    cout << endl << "ans = " << ans << endl;
    return ans;
}

int add_not(int x) {
    cout << "NOT" << endl;
    cout << 1 - a[x] << endl;
    return (1 - a[x]);
}*/

pair<int, int> FindFirst(int H, int W, int h1, int h2, int w1, int w2) {
    if(h1 == h2) {
        if(w1 == w2) {
            if(add_or({h1 * W + w1}) == 1) {
                return {h1, w1};
            }
            else {
                return {-1, -1};
            }
        }
        vector<int> x;
        for(int i = w1; i <= w2; i++ ){
            x.push_back(h1 * W + i);
        }
        if(add_or(x) == 0)
            return {-1, -1};
        int mid = (w1 + w2) / 2;
        pair<int, int> ans1 = FindFirst(H, W, h1, h2, w1, mid);
        if(ans1.first == -1)
            ans1 = FindFirst(H, W, h1, h2, mid + 1, w2);
        return ans1;
    }
    vector<int> x;
    for(int i = h1; i <= h2; i++) {
        for(int j = w1; j <= w2; j++) {
            x.push_back(i * W + j);
        }
    }
    if(add_or(x) == 0)
        return {-1, -1};
    int mid = (h1 + h2) / 2;
    pair<int, int> ans1 = FindFirst(H, W, h1, mid, w1, w2);
    if(ans1.first == -1) {
        ans1 = FindFirst(H, W, mid + 1, h2, w1, w2);
    }
    return ans1;
}

pair<int, int> FindSecond(int H, int W, int h1, int h2, int w1, int w2) {
    if(h1 == h2) {
        if(w1 == w2) {
            if(add_or({h1 * W + w1}) == 1) {
                return {h1, w1};
            }
            else {
                return {-1, -1};
            }
        }
        vector<int> x;
        for(int i = w1; i <= w2; i++) {
            x.push_back(h1 * W + i);
        }
        if(add_or(x) == 0)
            return {-1, -1};
        int mid = (w1 + w2) / 2;
        pair<int, int> ans1 = FindSecond(H, W, h1, h2, mid + 1, w2);
        if(ans1.first == -1)
            ans1 = FindSecond(H, W, h1, h2, w1, mid);
        return ans1;
    }
    vector<int> x;
    for(int i = h1; i <= h2; i++) {
        for(int j = w1; j <= w2; j++) {
            x.push_back(i * W + j);
        }
    }
    if(add_or(x) == 0)
        return {-1, -1};
    int mid = (h1 + h2) / 2;
    pair<int, int> ans1 = FindSecond(H, W, mid + 1, h2, w1, w2);
    if(ans1.first == -1) {
        ans1 = FindSecond(H, W, h1, mid, w1, w2);
    }
    return ans1;
}

void construct_network(int H, int W, int K) {
    pair<int, int> coordinates = FindFirst(H, W, 0, H - 1, 0, W - 1);
    //r1, c1
    pair<int, int> coordinates2 = FindSecond(H, W, 0, H - 1, 0, W - 1);
    //cout << coordinates.first << " " << coordinates.second << endl;
    //cout << coordinates2.first << " " << coordinates2.second << endl;
    int x = abs(coordinates2.first - coordinates.first) + abs(coordinates2.second - coordinates.second);
    if(x == K) {
        x = add_or({coordinates.first * W + coordinates.second});
    }
    else {
        x = add_not({coordinates.first * W + coordinates.second});
    }
   // cout << x << endl;
    return;
}

/*int main() {
    int h, w, k;
    cin >> h >> w >> k;
    while(true) {
        int r1;
        cin >> r1;
        if(r1 == -1)
            break;
        int c1, r2, c2;
        cin >> c1 >> r2 >> c2;
        MakeItGood(h, w);
        a[r1 * w + c1] = 1;
        a[r2 * w + c2] = 1;
        construct_network(h, w, k);
    }
}*/

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