Submission #1316385

#	Time	Username	Problem	Language	Result	Execution time	Memory
1316385		zhangspicyuwu	Towers (NOI22_towers)	C++20	16 / 100	2094 ms	23036 KiB

Main

#include <bits/stdc++.h>
#define int long long
#define fi first
#define se second
#define pii pair<int, int>
#define all(a) a.begin(), a.end()
using namespace std;

#ifdef LOCAL
#include "C:\Users\Dell\Downloads\template\template\icpc-notebook\Utilities\debug.h"
#else
#define debug(...) 42
#endif

const int mn = 5e5 + 5, mod = 1e9 + 7, inf = 2e9;

int n, x[mn], y[mn], cnt_x[mn], cnt_y[mn], max_x[mn], max_y[mn], min_x[mn], min_y[mn];

void trau(){
    for(int i = 0; i < n; i++){
        max_x[x[i]] = - inf, max_y[y[i]] = - inf;
        min_x[x[i]] = inf, min_y[y[i]] = inf;
    }
    int ans = -1;
    for(int mask = 0; mask < (1 << n); mask++){
        vector <int> on;
        for(int i = 0; i < n; i++){
            if(mask & (1 << i)) on.push_back(i);
        }

        for(auto i : on){
            cnt_x[x[i]] ++;
            cnt_y[y[i]] ++;
            max_x[x[i]] = max(max_x[x[i]], y[i]);
            min_x[x[i]] = min(min_x[x[i]], y[i]);
            max_y[y[i]] = max(max_y[y[i]], x[i]);
            min_y[y[i]] = min(min_y[y[i]], x[i]);
        }

        bool ok = true;
        for(auto i : on) if(cnt_x[x[i]] > 2 || cnt_y[y[i]] > 2) ok = false;
        if(ok){
            for(int i = 0; i < n; i++){
                if((max_x[x[i]] > y[i] && y[i] > min_x[x[i]]) || (max_y[y[i]] > x[i] && x[i] > min_y[y[i]]) || mask & (1 << i)) continue;
                ok = false;
            }
        }

        for(auto i : on){
            cnt_x[x[i]] --;
            cnt_y[y[i]] --;
            max_x[x[i]] = - inf, max_y[y[i]] = - inf;
            min_x[x[i]] = inf, min_y[y[i]] = inf;
        }
        if(ok){
            ans = mask;
            break;
        }
    }

    for(int i = 0; i < n; i++){
        if(ans & (1 << i)) cout << 1;
        else cout << 0;
    }
    cout << '\n';
}

void solve() {
    cin >> n;
    for(int i = 0; i < n; i++) cin >> x[i] >> y[i];
    trau();
}

signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);
    #define task "CSCH"
    if (fopen(task".INP", "r")) {
        freopen(task".INP", "r", stdin);
        freopen(task".OUT", "w", stdout);
    }
    int t = 1;
    // cin >> t;
    while (t--) solve();
    return 0;
}
// Don't wanna lose anymore T_T
// Never let me go - Kazuo Ishiguro

Compilation message (stderr)

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

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