Submission #224976

#	Time	Username	Problem	Language	Result	Execution time	Memory
224976		VEGAnn	Konj (COCI19_konj)	C++14	70 / 70	77 ms	7660 KiB

konj

#include <bits/stdc++.h>
#define sz(x) ((int)x.size())
#define pii pair<int,int>
#define MP make_pair
#define PB push_back
#define ft first
#define sd second
#define all(x) x.begin(),x.end()
using namespace std;
typedef long long ll;
const int N = 310;
const int oo = 2e9;
queue<pii> q;
pii hr[N][N], vr[N][N];
vector<array<int, 3> > hor, ver;
int n, min_x, max_x, min_y, max_y;
bool mrk[N][N];

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0);

//    freopen("in.txt","r",stdin);

    for (int i = 0; i < N; i++)
    for (int j = 0; j < N; j++){
        hr[i][j] = vr[i][j] = MP(oo, -oo);
    }

    cin >> n;

    for (int i = 0; i < n; i++){
        int a, b, c, d; cin >> a >> b >> c >> d;

        if (a != c){
            if (a > c) swap(a, c);
            ver.PB({b, a, c});
        } else {
            if (b > d) swap(b, d);
            hor.PB({a, b, d});
        }
    }

    sort(all(hor));

    for (int i = 0; i < sz(hor); ){
        int j = i, lst = hor[i][2];

        while (j < sz(hor) && hor[i][0] == hor[j][0] && hor[j][1] <= lst){
            lst = max(lst, hor[j][2]);
            j++;
        }

        for (int I = hor[i][1]; I <= lst; I++)
            hr[hor[i][0]][I] = MP(hor[i][1], lst);

        i = j;
    }

    sort(all(ver));

    for (int i = 0; i < sz(ver); ){
        int j = i, lst = ver[i][2];

        while (j < sz(ver) && ver[i][0] == ver[j][0] && ver[j][1] <= lst){
            lst = max(lst, ver[j][2]);
            j++;
        }

        for (int I = ver[i][1]; I <= lst; I++)
            vr[I][ver[i][0]] = MP(ver[i][1], lst);

        i = j;
    }

    int sx, sy; cin >> sx >> sy;

    q.push(MP(sx, sy));
    min_x = max_x = sx;
    min_y = max_y = sy;

    mrk[sx][sy] = 1;

    while (sz(q)){
        pii CR = q.front(); q.pop();
        int x = CR.ft, y = CR.sd;

        if (vr[x][y].ft < x && !mrk[x - 1][y]){
            min_x = min(min_x, x - 1);
            mrk[x - 1][y] = 1;
            q.push(MP(x - 1, y));
        }

        if (vr[x][y].sd > x && !mrk[x + 1][y]){
            max_x = max(max_x, x + 1);
            mrk[x + 1][y] = 1;
            q.push(MP(x + 1, y));
        }

        if (hr[x][y].ft < y && !mrk[x][y - 1]){
            min_y = min(min_y, y - 1);
            mrk[x][y - 1] = 1;
            q.push(MP(x, y - 1));
        }

        if (hr[x][y].sd > y && !mrk[x][y + 1]){
            max_y = max(max_y, y + 1);
            mrk[x][y + 1] = 1;
            q.push(MP(x, y + 1));
        }
    }

    for (int j = max_y; j >= min_y; j--) {
        for (int i = min_x; i <= max_x; i++)
            cout << (mrk[i][j] ? "#" : ".");
        cout << '\n';
    }

    return 0;
}

• Subtask 1: 70 / 70