제출 #1302368

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1302368		clue_	Towers (NOI22_towers)	C++20	23 / 100	293 ms	93472 KiB

Main

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

#define int long long
#define pp pair <int, int>
#define fi first
#define se second
#define yes cout << "YES\n"
#define no cout << "NO\n"

const int N = 1e6 + 9;
const int mod = 1e9 + 7;
const int INF = 1e18 + 9;

void add (int &a, int b){
	a += b;
	if (a >= mod) a -= mod;
}

void sub (int &a, int b){
	a -= b; 
	if (a < 0) a += mod;
}

int n;

struct point {
    int x;
    int y;
    int idx;
} pts[N];
int res[N];
vector <int> grpX[N], grpY[N];

int cntRow[N], cntCol[N];

namespace sub1 {
    bool check (int mask){
        int mx = 0;
        for (int i = 1; i <= n; i++) if (mask >> (i - 1) & 1){
            cntRow[pts[i].x]++; cntCol[pts[i].y]++;
            mx = max ({mx, cntRow[pts[i].x], cntCol[pts[i].y]});
        }
        for (int i = 1; i <= n; i++){
            cntRow[pts[i].x] = 0; cntCol[pts[i].y] = 0;
        }
        if (mx > 2){
            for (int i = 1; i <= n; i++){
                cntRow[pts[i].x] = 0; cntCol[pts[i].y] = 0;
            }
            return 0;
        }
        for (int i = 1; i <= n; i++){
            if (mask >> (i - 1) & 1) continue;
            int onL = 0, onR = 0;
            for (int idx : grpX[pts[i].x]){
                if ((mask >> (idx - 1) & 1) ^ 1) continue;
                if (pts[idx].y < pts[i].y) onL = 1;
                if (pts[idx].y > pts[i].y) onR = 1;
            }
            if (onL && onR) continue;
            onL = 0; onR = 0;
            for (int idx : grpY[pts[i].y]){
                if ((mask >> (idx - 1) & 1) ^ 1) continue;
                if (pts[idx].x < pts[i].x) onL = 1;
                if (pts[idx].x > pts[i].x) onR = 1;
            }
            if (onL && onR) continue;
            return 0;
        }
        return 1;
    }

    void solve (){
        for (int mask = 0; mask < (1 << n); mask++){
            if (check (mask)){
                for (int i = 0; i < n; i++) cout << (mask >> i & 1);
                exit (0);
            }
        }
        exit (0);
    }
}

namespace sub2 {
    bool valid (){
        for (int i = 1; i <= n; i++) if (grpX[pts[i].x].size () > 2) return 0;
        return 1;
    }

    void solve (){
        vector <int> res (n, 0);
        for (int i = 1; i <= 1000000; i++){
            if (grpY[i].empty ()) continue;
            res[grpY[i][0] - 1] = 1;
            res[grpY[i].back () - 1] = 1;
        }
        for (int i : res) cout << i;
        exit (0);
    }
}

int Ly[N], Ry[N];

bool needFill (int x){
    for (int i : grpX[x]){
        int y = pts[i].y;
        if (Ly[y] == -1 || Ry[y] == -1) return 1;
        if (Ly[y] < x && x < Ry[y]){

        } else return 1;
    }
    return 0;
}

void upd (int y, int x){
    if (Ly[y] == -1 || Ly[y] > x) Ly[y] = x;
    if (Ry[y] == -1 || Ry[y] < x) Ry[y] = x;
}

void solve (){
    cin >> n;
    for (int i = 1; i <= n; i++){
        cin >> pts[i].x >> pts[i].y;
        pts[i].idx = i;
    }
    for (int i = 1; i <= n; i++){
        grpX[pts[i].x].push_back (pts[i].idx);
        grpY[pts[i].y].push_back (pts[i].idx);
    }
    if (sub2::valid ()) sub2::solve ();
    if (n <= 16) sub1::solve ();
    for (int i = 1; i <= 1000000; i++) Ly[i] = Ry[i] = -1;
    for (int i = 1; i <= 1000000; i++) sort (grpX[i].begin (), grpX[i].end (), [&](int z1, int z2){
        return pts[z1].y < pts[z2].y;
    });
    vector <int> res (n, 0);
    int L = 1, R = 1000000;
    while (1){
        while (L <= R && needFill (L) == 0) L++;
        if (L > R) break;
        while (L <= R && needFill (R) == 0) R--;
        if (L > R) break;
        //
        int stL = 0, enL = 0;
        for (int i : grpX[L]){
            int y = pts[i].y;
            if (Ly[y] == -1 || Ry[y] == -1){
                stL = i; break;
            }
            if (Ly[y] < L && L < Ry[y]){
            } else {
                stL = i; break;
            }
        }
        for (int i = grpX[L].size () - 1; i >= 0; i--){
            int y = pts[grpX[L][i]].y;
            if (Ly[y] == -1 || Ry[y] == -1){
                enL = grpX[L][i]; break;
            }
            if (Ly[y] < L && L < Ry[y]){
            } else {
                enL = grpX[L][i]; break;
            }
        }
        res[pts[stL].idx - 1] = res[pts[enL].idx - 1] = 1;
        upd (pts[stL].y, pts[stL].x); upd (pts[enL].y, pts[enL].x);
        // phase 2
        int stR = 0, enR = 0;
        for (int i : grpX[R]){
            int y = pts[i].y;
            if (Ly[y] == -1 || Ry[y] == -1){
                stR = i; break;
            }
            if (Ly[y] < R && R < Ry[y]){
            } else {
                stR = i; break;
            }
        }
        for (int i = grpX[R].size () - 1; i >= 0; i--){
            int y = pts[grpX[R][i]].y;
            if (Ly[y] == -1 || Ry[y] == -1){
                enR = grpX[R][i]; break;
            }
            if (Ly[y] < R && R < Ry[y]){
            } else {
                enR = grpX[R][i]; break;
            }
        }
        res[pts[stR].idx - 1] = res[pts[enR].idx - 1] = 1;
        upd (pts[stR].y, pts[stR].x); upd (pts[enR].y, pts[enR].x);
        L++; R--;
    }
    for (int i : res) cout << i;
}

bool END;

void reset (){

}

signed main (){
	ios_base::sync_with_stdio (false);
	cin.tie (NULL);
	cout.tie (NULL);
    if (fopen ("slamp.inp", "r")){
        freopen ("slamp.inp", "r", stdin);
        freopen ("slamp.out", "w", stdout);
    }
    int t = 1; // cin >> t;
    while (t--){
        solve ();
        reset ();
    }
}

// <33

컴파일 시 표준 에러 (stderr) 메시지

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

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