Submission #1302373

#	Time	Username	Problem	Language	Result	Execution time	Memory
1302373		clue_	Towers (NOI22_towers)	C++20	22 / 100	383 ms	82800 KiB

Main

#include <bits/stdc++.h>

using namespace std;
using ll = long long;

#define int long long
#define pii pair<ll, ll>
#define fi first
#define se second

const ll N = 1e6 + 5, inf = 1e9, mod = 1e9 + 7, block = 320, lim = 20;

int n;
pii a[N];

string convert(int x) {
    string s = "";
    while(x > 0) {
        int val = x % 2;
        s += to_string(val);
        x /= 2;
    }
    reverse(s.begin(), s.end());
    return s;
}
int reconvert(string s) {
    reverse(s.begin(), s.end());
    int tt = 0;
    for (int i = 0; i < s.size(); i++) {
        int val = s[i] - '0';
        tt += val * (1ll << i);
    }
    return tt;
}

namespace sub1 {
    map <int, int> cnt1, cnt2; // hang, cot
    int cal(int mask) {
        cnt1.clear(), cnt2.clear();
        for (int i = 0; i < n; i++) {
            if ((mask >> i) & 1) {
                cnt1[a[i].fi]++, cnt2[a[i].se]++;
                if (cnt1[a[i].fi] > 2 || cnt2[a[i].se] > 2) return 0;
            }
        }
        for (int i = 0; i < n; i++) {
            if ((mask >> i) & 1) continue;
            else {
                int okL = 0, okR = 0;
                for (int j = 0; j < n; j++) { // xet 2 hang ngang
                    if ((mask >> j) & 1) {
                        if (a[j].fi == a[i].fi && a[j].se < a[i].se) okL = 1;
                        if (a[j].fi == a[i].fi && a[j].se > a[i].se) okR = 1;
                    }
                }
                if (okL && okR) continue;
                int okU = 0, okD = 0;
                for (int j = 0; j < n; j++) { // xet 2 hang doc
                    if ((mask >> j) & 1) {
                        if (a[j].se == a[i].se && a[j].fi < a[i].fi) okU = 1;
                        if (a[j].se == a[i].se && a[j].fi > a[i].fi) okD = 1;
                    }
                }
                if (okU && okD) continue;
                return 0;
            }
        }
        return 1;
    }
    void solve() {
        // cout << reconvert("101010101") << '\n';
        for (int mask = 0; mask < (1 << n); mask++) {
            // cout << mask << '\n';
            // if (mask == 341) cout << cal(mask) << '\n';
            if (cal(mask)) {
                for (int i = 0; i < n; i++) {
                    if ((mask >> i) & 1) cout << 1;
                    else cout << 0;
                }
                return;
            }
        }
    }
}

namespace sub2 {
    vector <pii> pre[N];
    int On[N];
    void solve() { // for qua tat ca cac cot
        vector <int> comp;
        for (int i = 0; i < n; i++) {
            pre[a[i].se].emplace_back(a[i].fi, i);
            comp.push_back(a[i].se);
        }
        sort(comp.begin(), comp.end());
        comp.erase(unique(comp.begin(), comp.end()), comp.end());
        for (int i = 0; i < comp.size(); i++) {
            int idx = comp[i];
            sort(pre[idx].begin(), pre[idx].end());
        }
        for (int i = 0; i < comp.size(); i++) {
            int idx = comp[i];
            if (pre[idx].size() == 1) {
                On[pre[idx].back().se] = 1;
                continue;
            }
            else {
                int L = pre[idx][0].se;
                int R = pre[idx].back().se;
                On[L] = 1, On[R] = 1;
                continue;
            }
        }
        for (int i = 0; i < n; i++) cout << On[i];
    }
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    if (fopen("slamp.inp", "r")) {
        freopen("slamp.inp", "r", stdin);
        freopen("slamp.out", "w", stdout);
    }
    cin >> n;
    for (int i = 0; i < n; i++) cin >> a[i].fi >> a[i].se;
    // sub2::solve(); return 0;
    if (n <= 16) {
        sub1::solve();
    }
    else sub2::solve();
    return 0;
}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:122:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  122 |         freopen("slamp.inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:123:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  123 |         freopen("slamp.out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 5 / 5
• Subtask 2: 11 / 11
• Subtask 3: 0 / 7
• Subtask 4: 6 / 6
• Subtask 5: 0 / 31
• Subtask 6: 0 / 21
• Subtask 7: 0 / 19