Submission #1216351

#	Time	Username	Problem	Language	Result	Execution time	Memory
1216351		Peti	Card Collection (JOI24_collection)	C++20	0 / 100	4094 ms	452 KiB

Main

#include <bits/stdc++.h>
 
using namespace std;
 
const int MAXN = 200'001;
 
int s[MAXN], v[MAXN];
 
int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    
    int n, q; cin >> n >> q;
    for (int i = 1; i <= n; i++) cin >> s[i] >> v[i];
 
    set<pair<int, int>> ok;
 
    for (int i = 1; i <= n; i++) {
        for (int bits = 0; bits < (1<<(n-1)); bits++) {
            int ptr = 0;
            int x = s[i], y = v[i];
            for (int j = i+1; j <= n; j++) {  
                if (bits & (1<<(ptr++))) {
                    x = max(x, s[j]);
                    y = max(y, v[j]);
                } else {
                    x = min(x, s[j]);
                    y = min(y, v[j]);
                }
            }
            for (int j = i-1; j >= 1; j--) {  
                if (bits & (1<<(ptr++))) {
                    x = max(x, s[j]);
                    y = max(y, v[j]);
                } else {
                    x = min(x, s[j]);
                    y = min(y, v[j]);
                }
            }
            ok.insert({x, y});
        }
    }
 
    for (int l = 1; l <= n; l++) {
        for (int r = l+1; r <= n; r++) {
            for (int k = l+1; k <= r; k++) {
                for (int bits = 0; bits < (1<<(n-1)); bits++) {
                    int ptr = 0;
                    int x1 = s[r], y1 = v[r];
                    int x2 = s[l], y2 = v[l];
                    for (int j = r+1; j <= n; j++) {  
                        if (bits & (1<<(ptr++))) {
                            x1 = max(x1, s[j]);
                            y1 = max(y1, v[j]);
                        } else {
                            x1 = min(x1, s[j]);
                            y1 = min(y1, v[j]);
                        }
                    }
                    for (int j = r-1; j >= k; j--) {  
                        if (bits & (1<<(ptr++))) {
                            x1 = max(x1, s[j]);
                            y1 = max(y1, v[j]);
                        } else {
                            x1 = min(x1, s[j]);
                            y1 = min(y1, v[j]);
                        }
                    }
                    for (int j = l+1; j < k; j++) {  
                        if (bits & (1<<(ptr++))) {
                            x2 = max(x2, s[j]);
                            y2 = max(y2, v[j]);
                        } else {
                            x2 = min(x2, s[j]);
                            y2 = min(y2, v[j]);
                        }
                    }
                    for (int j = l-1; j >= 1; j--) {  
                        if (bits & (1<<(ptr++))) {
                            x2 = max(x2, s[j]);
                            y2 = max(y2, v[j]);
                        } else {
                            x2 = min(x2, s[j]);
                            y2 = min(y2, v[j]);
                        }
                    }
                    int x, y;
                    if (bits & (1<<(ptr++))) {
                        x = max(x1, x2);
                        y = max(y1, y2);
                    } else {
                        x = min(x1, x2);
                        y = min(y1, y2);
                    }
                    ok.insert({x, y});
                }
            }
        }
    }
    
    for (int i = 1; i <= q; i++) {
        int x, y; cin >> x >> y;
        if (ok.count({x, y})) {
            cout << i << " ";
        }
    }
 
    return 0;
}

• Subtask 1: 0 / 11
• Subtask 2: 0 / 38
• Subtask 3: 0 / 22
• Subtask 4: 0 / 29