oj.uz

Submission #336494

# Submission time Handle Problem Language Result Execution time Memory
336494 2020-12-15T12:51:51 Z aryan12 Vision Program (IOI19_vision) C++17
0 / 100
 2 ms 872 KB 
#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 - 1; i++) {
        a[i] = 0;
    }
}

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

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

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

int add_not(int x) {
    //cout << 1 - x << endl;
    return (1 - 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, 0, W);
    //r1, c1
    pair<int, int> coordinates2 = FindSecond(H, W, 0, H, 0, W);
    //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.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 492 KB WA in grader: Invalid index
2 Halted 0 ms 0 KB -

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 492 KB WA in grader: Invalid index
2 Halted 0 ms 0 KB -

Subtask #3
0 / 11.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 492 KB WA in grader: Invalid index
2 Halted 0 ms 0 KB -

Subtask #4
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 492 KB WA in grader: Invalid index
2 Halted 0 ms 0 KB -

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 364 KB WA in grader: Invalid index
2 Halted 0 ms 0 KB -

Subtask #6
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 364 KB WA in grader: Invalid index
2 Halted 0 ms 0 KB -

Subtask #7
0 / 14.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 872 KB WA in grader: Invalid index
2 Halted 0 ms 0 KB -

Subtask #8
0 / 19.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 492 KB WA in grader: Invalid index
2 Halted 0 ms 0 KB -