제출 #1302340

#제출 시각아이디문제언어결과실행 시간메모리
1302340ndquangTowers (NOI22_towers)C++20
16 / 100
111 ms25944 KiB
#include <bits/stdc++.h>
using namespace std;

#define int long long
#define pb push_back
#define fi first
#define sc second
#define all(x) (x).begin(), (x).end()
#define Bit(x, y) ((x >> y) & 1)
#define inpFile(Task) freopen(Task".inp", "r", stdin);
#define outFile(Task) freopen(Task".out", "w", stdout);
#define submitFile(Task) inpFile(Task); outFile(Task);

using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using ull = unsigned ll;
const ll INF = (int)1e18, MOD1 = (int)1e9 + 7, MOD2 = (int)998244353;
template<class X, class Y> void maximize(X &a, const Y &b) { a = (a < b) ? b : a; }
template<class X, class Y> void minimize(X &a, const Y &b) { a = (a > b) ? b : a; }
template<class T> void add(T& a, T b, T mod) { a += b; if(a >= mod) a -= mod; }
template<class T> void sub(T& a, T b, T mod) { a -= b; if(a <= 0) a += mod; }

const int maxn = (int)1e6 + 8;

int n;
int x[maxn], y[maxn];

namespace subtask2 {
    void solve() {
        for(int mask = 0; mask < (1 << n); mask++) {
            map<int, int> cntX, cntY;
            bool ok = 1;
            for(int i = 1; i <= n; i++) {
                if(!(mask & (1 << (i - 1)))) continue;
                cntX[x[i]]++;
                cntY[y[i]]++;
                if(cntX[x[i]] > 2 || cntY[y[i]] > 2) {
                    ok = 0;
                    break;
                }
            }
            if(!ok) continue;
            for(int i = 1; i <= n && ok; i++) {
                if(mask & (1 << (i - 1))) continue;
                bool dong = 0, tay = 0, nam = 0, bac = 0;
                for(int j = 1; j <= n; j++) {
                    if(!(mask & (1 << (j - 1)))) continue;
                    if(x[j] == x[i]) {
                        if(y[j] < y[i]) bac = 1;
                        if(y[j] > y[i]) nam = 1;
                    }
                    if(y[j] == y[i]) {
                        if(x[j] < x[i]) tay = 1;
                        if(x[j] > x[i]) dong = 1;
                    }
                }
                if(!((nam && bac) || (dong && tay))) ok = 0;
            }

            if(ok) {
                for (int i = 1; i <= n; i++) cout << ((mask & (1 << (i - 1))) ? '1' : '0');
                cout << "\n";
                return;
            }
        }
    }
}

signed main() {
    cin.tie(0)->ios_base::sync_with_stdio(0);
    //submitFile("slamp");
    cin >> n;
    for(int i = 1; i <= n; i++) cin >> x[i] >> y[i];
    subtask2::solve();
    return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...