Submission #1307281

#	Time	Username	Problem	Language	Result	Execution time	Memory
1307281		nanaseyuzuki	Towers (NOI22_towers)	C++20	100 / 100	1653 ms	136448 KiB

Main

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

const int mn = 1e6 + 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 << 16); 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';
}
namespace sub1e5{
	struct Tower{
		int id, x, y;

		bool operator<(const Tower& other) const {
	        return y != other.y ? y < other.y : x < other.x;
	    }
	} e[mn];

	vector<Tower> a[mn];
	int l[mn], r[mn], on[mn], id[mn];

	bool cmp(int i, int j){
		return y[i] < y[j];
	}

	int get(int pos, int val){
		return lower_bound(a[pos].begin(), a[pos].end(), Tower{-1, pos, val}) - a[pos].begin();
	}

	void del_bottom(int type){
		priority_queue<int> c[mn];

		for(int i = 0; i < n; i++){
			if(on[i]) c[y[i]].push(x[i]);
		}

		for(int i = 1; i <= 1000000; i++) id[i] = a[i].size() - 1;

		for(int i = 1000000; i >= 1; i--){
			if(c[i].empty()) continue;

			// Giữ đỉnh cao nhất
			id[c[i].top()]--;
			c[i].pop();

			while(c[i].size() > 1){
				int cur = c[i].top(); c[i].pop();
				id[cur] = get(cur, i);

				if(id[cur] - type < 0) continue;
				if(on[a[cur][id[cur]].id] == 0) continue;

				on[a[cur][id[cur]].id] = 0;
				id[cur]--;

				if(id[cur] >= 0 && on[a[cur][id[cur]].id] == 0){
					c[a[cur][id[cur]].y].push(cur);
					on[a[cur][id[cur]].id] = 1;
				}
			}

			if(!c[i].empty()){
	            id[c[i].top()]--;
	            c[i].pop();
	        }
		}
	}

	void del_up(int type){
		priority_queue<int> c[mn];

		for(int i = 0; i < n; i++){
			if(on[i]) c[y[i]].push(x[i]);
		}

		for(int i = 1; i <= 1000000; i++) id[i] = 0;

		for(int i = 1; i <= 1000000; i++){
			if(c[i].empty()) continue;

			c[i].pop();

			while(c[i].size() > 1){
				int cur = c[i].top(); c[i].pop();
				id[cur] = get(cur, i);

				if(id[cur] + type >= (int)a[cur].size()) continue;
				if(on[a[cur][id[cur]].id] == 0) continue;

				on[a[cur][id[cur]].id] = 0;
				id[cur]++;

				if(id[cur] < (int)a[cur].size() && on[a[cur][id[cur]].id] == 0){
					c[a[cur][id[cur]].y].push(cur);
					on[a[cur][id[cur]].id] = 1;
				}
			}

			if(!c[i].empty()){
            	id[c[i].top()]--;
        	    c[i].pop();
		    }
		}
	}

	void sol(){
		for(int i = 0; i < n; i++) e[i] = {i, x[i], y[i]};
		sort(e, e + n);
		for(int i = 0; i < n; i++) a[e[i].x].push_back(e[i]);

		for(int i = 1; i <= 1000000; i++){
			if(a[i].size()){
				sort(a[i].begin(), a[i].end());
				on[a[i].front().id] = 1;
				on[a[i].back().id]  = 1;
			}
		}

		for(int i = 1; i <= 4; i++){
			del_up(1);
			del_bottom(1);
		}
		del_up(0);
		del_bottom(0);

		for(int i = 0; i < n; i++) cout << on[i];
		cout << '\n';
	}
}

void solve(){
    cin >> n;
    for(int i = 0; i < n; i ++) cin >> x[i] >> y[i];
    if(n <= 16) trau();
	else{
		for(int i = 0; i < n; i++){
		    max_y[y[i]] = -inf;
		    min_y[y[i]] = inf;
		}


		for(int i = 0; i < n; i++) cnt_x[x[i]] ++;
		bool sub3 = true;
		for(int i = 0; i < n; i++){
			if(cnt_x[x[i]] > 2) sub3 = false;
		}
		if(sub3){
			vector <int> on(n + 1, 0);
			for(int i = 0; i < n; i++){
				max_y[y[i]] = max(max_y[y[i]], x[i]);
				min_y[y[i]] = min(min_y[y[i]], x[i]);
			}
			int qq = 0;
			for(int i = 0; i < n; i++){
				if(x[i] == max_y[y[i]] || x[i] == min_y[y[i]]){
					on[i] = 1;
					qq ++;
				}
			}
			// cout << qq << '\n';
			for(int i = 0; i < n; i++) cout << on[i];
			cout << '\n';
		}
		else sub1e5::sol();
	}
}

main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);
    if (fopen("SLAMP.INP", "r")) {
        freopen("SLAMP.INP", "r", stdin);
        freopen("SLAMP.OUT", "w", stdout);
    }
    int t = 1;
    // cin >> t;
    while (t--) solve();
    return 0;
}

Compilation message (stderr)

Main.cpp:220:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
  220 | main() {
      | ^~~~
Main.cpp: In function 'int main()':
Main.cpp:224:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  224 |         freopen("SLAMP.INP", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:225:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  225 |         freopen("SLAMP.OUT", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~

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