Submission #1302337

#	Time	Username	Problem	Language	Result	Execution time	Memory
1302337		flo	Towers (NOI22_towers)	C++20	11 / 100	656 ms	116240 KiB

Main

#include <bits/stdc++.h>
#define task "testing"
#define ll long long
#define multitest 0
using namespace std;

struct Point {
	int x, y;
};

const int N = 1e6;

Point p[N+5];

bool ans[N+5];

int cntx[N+5], cnty[N+5];

vector<int> dx, dy, X[N+5], Y[N+5];

bool cmpx(int x, int y) {
	return p[x].x < p[y].x;
}

bool cmpy(int x, int y) {
	return p[x].y < p[y].y;
}

void on(int i) {
	if (ans[i]) return;
	
	cntx[p[i].x]++;
	cnty[p[i].y]++;
	
	ans[i] = 1;
}

void off(int i) {
	if (!ans[i]) return;
	
	cntx[p[i].x]--;
	cnty[p[i].y]--;
	
	ans[i] = 0;
}

void flo(int ID) {
	int n; cin >> n;
	
	for (int i = 1; i <= n; i++) {
		cin >> p[i].x >> p[i].y;
		
		dx.push_back(p[i].x);
		dy.push_back(p[i].y);
		
		X[p[i].x].push_back(i);
		Y[p[i].y].push_back(i);
	}
	
	sort(dx.begin(), dx.end());
	sort(dy.begin(), dy.end());
	
	dx.resize(unique(dx.begin(), dx.end())-dx.begin());
	dy.resize(unique(dy.begin(), dy.end())-dy.begin());
	
	for (auto x : dx) {
		sort(X[x].begin(), X[x].end(), cmpy);
		
		on(X[x][0]), on(X[x].back());
	}
	
	for (auto y : dy) {
		sort(Y[y].begin(), Y[y].end(), cmpx);
		
		on(Y[y][0]), on(Y[y].back());
	}
	
	for (auto x : dx) {
		for (int i = 0; i < X[x].size(); i++) {
			if (cnty[p[X[x][i]].y] <= 2) break;
			
			if (X[x][i] == Y[p[X[x][i]].y][0] || X[x][i] == Y[p[X[x][i]].y].back()) continue;
			
			off(X[x][i]);
			
			if (i+1 < X[x].size()) {
				on(X[x][i+1]);
			}
		}
		
		for (int i = X[x].size()-1; i >= 0; i--) {
			if (cnty[p[X[x][i]].y] <= 2) break;
			
			if (X[x][i] == Y[p[X[x][i]].y][0] || X[x][i] == Y[p[X[x][i]].y].back()) continue;
			
			off(X[x][i]);
			
			if (i > 0) {
				on(X[x][i-1]);
			}
		}
	}
	
	for (auto y : dy) {
		for (int i = 0; i < Y[y].size(); i++) {
			if (cntx[p[Y[y][i]].x] <= 2) break;
			
			if (Y[y][i] == X[p[Y[y][i]].x][0] || Y[y][i] == X[p[Y[y][i]].x].back()) continue;
			
			off(Y[y][i]);
			
			if (i+1 < Y[y].size()) {
				on(Y[y][i+1]);
			}
		}
		
		for (int i = Y[y].size()-1; i >= 0; i--) {
			if (cntx[p[Y[y][i]].x] <= 2) break;
			
			if (Y[y][i] == X[p[Y[y][i]].x][0] || Y[y][i] == X[p[Y[y][i]].x].back()) continue;
			
			off(Y[y][i]);
			
			if (i > 0) {
				on(Y[y][i-1]);
			}
		}
	}
	
	for (int i = 1; i <= n; i++) cout << ans[i];
	
	cout << "\n";
}

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);

	if (fopen(task".inp", "r")) {
		freopen(task".inp", "r", stdin);
		freopen(task".out", "w", stdout);
	}

	int TCS = 1, ID = 1;

	if (multitest) {
		cin >> TCS;
	}

	while (TCS--) flo(ID++);

	return 0;
}

Compilation message (stderr)

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

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