oj.uz

Submission #362610

# Submission time Handle Problem Language Result Execution time Memory
362610 2021-02-03T17:50:24 Z mihai145 Vision Program (IOI19_vision) C++14
0 / 100
 52 ms 5096 KB 
#include "vision.h"
#include <vector>

using namespace std;

const int NMAX = 400;
const int CT = 200;

int _H, _W;

int Get_Index(int x, int y) {
    return x * _W + y;
}

vector<int> diagPlus[NMAX + 5], diagMinus[NMAX + 5];
int resDiagPlus[NMAX + 5], resDiagMinus[NMAX + 5];
int prefPlus[NMAX + 5], sufPlus[NMAX + 5];
int prefMinus[NMAX + 5], sufMinus[NMAX + 5];

void construct_network(int H, int W, int K) {
    _H = H;
    _W = W;

    for (int i = 0; i < H; i++)
        for (int j = 0; j < W; j++) {
            diagPlus[i + j].push_back(Get_Index(i, j));
            diagMinus[i - j + CT].push_back(Get_Index(i, j));
        }

    ///DiagPlus
    for (int i = 0; i <= H + W; i++)
        if ((int) diagPlus[i].size() > 0) {
            vector<int> Ns;
            for (auto it : diagPlus[i])
                Ns.push_back(it);
            if ((int) Ns.size() > 0)
                resDiagPlus[i] = add_or(Ns);
        }

    ///DiagMinus
    for (int i = -W; i <= H; i++)
        if ((int) diagMinus[i + CT].size() > 0) {
            vector<int> Ns;
            for (auto it : diagMinus[i + CT])
                Ns.push_back(it);
            if ((int) Ns.size() > 0)
                resDiagMinus[i + CT] = add_or(Ns);
        }

    ///DiagPlus L->R
    for (int i = 0; i <= H + W; i++)
        if ((int) diagPlus[i].size() > 0) {
            ///Prefix OR 0...i
            vector<int> Ns;
            for (int j = 0; j <= i; j++) {
                Ns.push_back(resDiagPlus[j]);
            }
            if ((int) Ns.size() > 0)
                prefPlus[i] = add_or(Ns);
        }

    ///DiagPlus R->L
    for (int i = H + W - 2; i >= 0; i--) {
        ///Suffix OR i...H+W-2
        vector<int> Ns;
        for (int j = i; j <= H + W - 2; j++) {
            Ns.push_back(resDiagPlus[j]);
        }
        if ((int) Ns.size() > 0)
            sufPlus[i] = add_or(Ns);
    }

    ///DiagMinus L->R
    for (int i = -W + 1; i <= H - 1; i++) {
        ///Prefix OR -W+1...i
        vector<int> Ns;
        for (int j = -W + 1; j <= i; j++) {
            Ns.push_back(resDiagMinus[j + CT]);
        }
        if ((int) Ns.size() > 0)
            prefMinus[i + CT] = add_or(Ns);
    }

    ///DiagMinus R->L
    for (int i = H - 1; i >= -W + 1; i--) {
        ///Suffix OR i...H-1
        vector<int> Ns;
        for (int j = i; j <= H - 1; j++) {
            Ns.push_back(resDiagMinus[j + CT]);
        }
        if ((int) Ns.size() > 0)
            sufMinus[i + CT] = add_or(Ns);
    }

    ///CASE 1: diagPlus is 1 at a distance of K and diagMinus is 1 at a distance of at most K
    ///CODE HERE...
    int res1 = -1;
    vector<int> resAnds;
    for (int i = 0; i <= W + H - 2 - K; i++) {
        vector<int> Ns;
        Ns.push_back(resDiagPlus[i]);
        Ns.push_back(resDiagPlus[i + K]);
        resAnds.push_back(add_and(Ns));
    }

    int isDiagPlusAtDistanceK = -1;
    if((int)resAnds.size() > 0) {
        isDiagPlusAtDistanceK = add_or(resAnds);
    }

    resAnds.clear();
    for (int l = -W + 1; l <= H - 1 - K; l++) {
        vector<int> Ns;
        if (l - 1 >= -W + 1) {
            Ns.push_back(prefMinus[l - 1 + CT]);
        }
        if (l + K + 1 <= H - 1) {
            Ns.push_back(sufMinus[l + K + 1 + CT]);
        }
        if ((int) Ns.size() > 0) {
            int fsp = add_or(Ns);
            resAnds.push_back(add_not(fsp));
        }
    }

    int isDiagMinusAtDistanceAtMostK = -1;
    if((int)resAnds.size() > 0) {
        isDiagMinusAtDistanceAtMostK = add_or(resAnds);
    }

    if(isDiagPlusAtDistanceK != -1 && isDiagMinusAtDistanceAtMostK != -1) {
        res1 = add_and({isDiagPlusAtDistanceK, isDiagMinusAtDistanceAtMostK});
    }

    ///CASE 2: diagMinus is 1 at a distance of K and diagPlus is 1 at a distance of at most K
    ///CODE HERE...
    int res2 = -1;
    resAnds.clear();
    for (int i = -W + 1; i <= H - 1 - K; i++) {
        vector<int> Ns;
        Ns.push_back(resDiagMinus[i + CT]);
        Ns.push_back(resDiagMinus[i + K + CT]);
        resAnds.push_back(add_and(Ns));
    }

    int isDiagMinusAtDistanceK = -1;
    if((int)resAnds.size() > 0) {
        isDiagMinusAtDistanceK = add_or(resAnds);
    }

    resAnds.clear();
    for (int l = 0; l <= H + W - 2 - K; l++) {
        vector<int> Ns;
        if (l - 1 >= 0) {
            Ns.push_back(prefPlus[l - 1]);
        }
        if (l + K + 1 <= H + W - 2) {
            Ns.push_back(sufPlus[l + K + 1]);
        }
        if ((int) Ns.size() > 0) {
            int fsp = add_or(Ns);
            resAnds.push_back(add_not(fsp));
        }
    }


    int isDiagPlusAtDistanceAtMostK = -1;
    if((int)resAnds.size() > 0) {
        isDiagPlusAtDistanceAtMostK = add_or(resAnds);
    }

    if(isDiagMinusAtDistanceK != -1 && isDiagPlusAtDistanceAtMostK != -1) {
        res2 = add_and({isDiagMinusAtDistanceK, isDiagPlusAtDistanceAtMostK});
    }

    if(res1 != -1 && res2 != -2) {
        add_or({res1, res2});
    } else if(res1 != -1) {
        int finalRes = add_not(res1);
        add_not(finalRes);
    } else {
        int finalRes = add_not(res2);
        add_not(finalRes);
    }

    /*
	std::vector<int> Ns;
	Ns = {0, 1};
	int a = add_and(Ns);
	Ns = {0, a};
	int b = add_or(Ns);
	Ns = {0, 1, b};
	int c = add_xor(Ns);
	add_not(c);
    */
}

Subtask #1
0 / 10.0

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

Subtask #2
0 / 11.0

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

Subtask #3
0 / 11.0

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

Subtask #4
0 / 15.0

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

Subtask #5
0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 1260 KB Output is correct
2 Correct 11 ms 1132 KB Output is correct
3 Correct 13 ms 1132 KB Output is correct
4 Incorrect 2 ms 748 KB WA in grader: Invalid index
5 Halted 0 ms 0 KB -

Subtask #6
0 / 8.0

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

Subtask #7
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 52 ms 5096 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 6 ms 876 KB Output is correct
4 Correct 10 ms 1260 KB Output is correct
5 Correct 10 ms 1260 KB Output is correct
6 Correct 10 ms 1260 KB Output is correct
7 Correct 27 ms 2924 KB Output is correct
8 Correct 27 ms 3052 KB Output is correct
9 Correct 48 ms 5096 KB Output is correct
10 Incorrect 0 ms 364 KB WA in grader: Invalid index
11 Halted 0 ms 0 KB -

Subtask #8
0 / 19.0

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