Submission #1237644

#	Time	Username	Problem	Language	Result	Execution time	Memory
1237644		bangan	Mosaic (IOI24_mosaic)	C++20	0 / 100	94 ms	15016 KiB

mosaic

#include "mosaic.h"
#include <bits/stdc++.h>
#include <vector>
using namespace std;

#define ll long long

#define pb push_back

#define LC (v<<1)
#define RC (v<<1|1)
#define mid ((l+r) >> 1)

std::vector<long long> mosaic(std::vector<int> X, std::vector<int> Y, std::vector<int> T, std::vector<int> B, std::vector<int> L, std::vector<int> R) {
	int n = X.size();
	int q = (int)T.size();
    if (n==1) return vector<ll> (q, X[0]);

    vector<ll> ans(q);
    vector<int> all(q);
    iota(all.begin(), all.end(), 0);
    sort(all.begin(), all.end(), [&](int i, int j) {
        return T[i]<T[j];
    });
    auto it = all.begin();

    vector<int> a;
    for (int i=1; i<n; i++) a.pb(X[i]);

    for (int r=0; r<1; r++) {
        while (it!=all.end() && T[*it]==r) {
            int c = L[*it];
            if (c==0) ans[*it] = Y[r];
            else ans[*it] = a[c-1];
            it++;
        }

        if (r+1 != n) {
            vector<int> b;
            b.pb((Y[r+1]|a[0])^1);
            for (int i=1; i<a.size(); i++) b.pb((b.back()|a[i])^1);
            swap(a, b);
        }
    }

    {
        vector<int> b = a;
        a.clear();
        for (int i=0; i<n; i++) a.pb(0);
        for (int i:b) a.pb(i);
    }
    int z=n;

    for (int r=1; r<n; r++) {
        while (it!=all.end() && T[*it]==r) {
            int c = L[*it];
            if (c==0) ans[*it] = Y[r];
            else ans[*it] = a[z+c-1];
            it++;
        }
        
        if (r+1 != n) {
            z--;
            a[z] = (Y[r+1]|a[z+1])^1;
        }
    }
    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