Submission #1225363

#	Time	Username	Problem	Language	Result	Execution time	Memory
1225363		VMaksimoski008	모자이크 (IOI24_mosaic)	C++20	0 / 100	1100 ms	111452 KiB

mosaic

#include "mosaic.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;

vector<ll> mosaic(vector<int> x, vector<int> y, vector<int> t, vector<int> b, vector<int> l, vector<int> r) {
    int n = x.size(), q = t.size();
    vector<ll> ans(q);

    queue<pii> Q;
    map<pii, int> val;
    for(int i=0; i<n; i++) {
        val[{ 0, i }] = x[i];
        val[{ i, 0 }] = y[i];
    }
    Q.push({ 1, 1 });
    val[{ 1, 1 }] = (val[{ 0, 1 }] + val[{ 1, 0 }] == 0);

    int vis = 0;
    while(!Q.empty()) {
        auto [r, c] = Q.front(); Q.pop();
        vis++;
        if(min(r+1, c) <= 3 && max(r+1, c) < n && !val.count({ r+1, c })) {
            val[{ r+1, c }] = (val[{ r, c }] + val[{ r+1, c-1 }] == 0);
            Q.push({ r+1, c });
        }
        if(min(r, c+1) <= 3 && max(r, c+1) < n && !val.count({ r, c+1 })) {
            val[{ r, c+1 }] = (val[{ r, c }] + val[{ r-1, c+1 }] == 0);
            Q.push({ r, c+1 });
        }
    }
    assert(vis <= 7*n);

    // for(int i=0; i<n; i++) {
    //     for(int j=0; j<n; j++) cout << val[{ i, j }] << " ";
    //     cout << endl;
    // }

    for(int i=0; i<q; i++) {
        int r = t[i], c = l[i];
        if(min(r, c) <= 2) {
            ans[i] = val[{ r, c }];
        } else {
            int cnt = min(r-3, c-3);
            ans[i] = val[{r-cnt, c-cnt}];
        }
    }

    return ans;
}

• Subtask 0: 0 / 0
• Subtask 1: 0 / 5
• Subtask 2: 0 / 7
• Subtask 3: 0 / 7
• Subtask 4: 0 / 10
• Subtask 5: 0 / 8
• Subtask 6: 0 / 22
• Subtask 7: 0 / 19
• Subtask 8: 0 / 22