제출 #1302561

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1302561		tminh	Towers (NOI22_towers)	C++20	16 / 100	433 ms	35692 KiB

Main

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

#define task "SLAMP"
#define ll long long
#define endl '\n'
#define x first
#define y second
#define vall(a) (a).begin(), (a).end()
#define sze(a) (int)a.size()
#define pii pair<int, int>
#define pll pair<ll, ll>


#define ep emplace_back
#define pb push_back
#define pf push_front


const ll mod = 1e9 + 7;
const int N = 2e6 + 5;
const ll oo = 1e18;


int n, m;
pii a[N];
vector<int> arr;

namespace sub2 {
	
	int ans[N], b[N];
	vector<int> sadx[N], sady[N];
	bool kt() {
		for (int i = 0; i < m; ++i) {
			sadx[i].clear();
			sady[i].clear();
		}
		
		
		for (int i = 1; i <= n; ++i) {
			if (b[i]) {
				sadx[a[i].x].pb(a[i].y);
				sady[a[i].y].pb(a[i].x);
			}
		}
		for (int i = 0; i < m; ++i) {
			if (sze(sadx[i]) > 2 || sze(sady[i]) > 2) return false;
			sort(vall(sadx[i]));
			sort(vall(sady[i]));
		}
		
		for (int i = 1; i <= n; ++i) {
			bool flag = false;
			auto it1 = lower_bound(vall(sadx[a[i].x]), a[i].y);
			auto it2 = upper_bound(vall(sadx[a[i].x]), a[i].y);
			if (it1 != sadx[a[i].x].end() && it2 != sadx[a[i].x].begin()) flag = true;
			
			it1 = lower_bound(vall(sady[a[i].y]), a[i].x);
			it2 = upper_bound(vall(sady[a[i].y]), a[i].x);
			if (it1 != sady[a[i].y].end() && it2 != sady[a[i].y].begin()) flag = true;
			
			if (!flag) return false;
		}
		for (int i = 1; i <= n; ++i) ans[i] = b[i];
		return true;
	}
	
	
	bool bt(int i) {
		if (i == n + 1) return kt();
		
		b[i] = 0;
		if (bt(i + 1)) return true;
		
		
		b[i] = 1;
		if (bt(i + 1)) return true;
		
		return false;
	}
		
	void solve() {
		bt(1);
		for (int i = 1; i <= n; ++i) cout << ans[i];	
	}
	bool check() {
		return n <= 20;
	}
}

namespace sub3 {
	bool ans[N];
	vector<pii> sad[N];
	void solve() {
		for (int i = 1; i <= n; ++i) sad[a[i].y].pb(make_pair(a[i].x, i));
	    
		for (int i = 0; i < m; ++i) {
			if (!sad[i].empty()) {
				ans[sad[i].back().y] = true;
				ans[sad[i][0].y] = true;
			}
		}
		
		for (int i = 1; i <= n; ++i) cout << ans[i];
	}
}




inline void solve() {
	sort(vall(arr));
	arr.erase(unique(vall(arr)), arr.end());
	for (int i = 1; i <= n; ++i) {
		a[i].x = lower_bound(vall(arr), a[i].x) - arr.begin();
		a[i].y = lower_bound(vall(arr), a[i].y) - arr.begin();
 	}
 	m = sze(arr);
 	
 	
	if (sub2::check()) return sub2::solve(); 
	return sub3::solve();
}


inline void input() {
    cin >> n;
    for (int i = 1; i <= n; ++i) {
    		cin >> a[i].x >> a[i].y;
    		arr.pb(a[i].x);
    		arr.pb(a[i].y);
    }
    return solve();
}

int main() {
    if(fopen(task ".inp", "r")) {
        freopen(task ".inp", "r", stdin);
        freopen(task ".out", "w", stdout);
    }
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);

    input();
    return 0;
}
//2911

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

Main.cpp: In function 'int main()':
Main.cpp:138:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  138 |         freopen(task ".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:139:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  139 |         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