제출 #1302375

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1302375		flo	Towers (NOI22_towers)	C++20	22 / 100	671 ms	116224 KiB

Main

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

struct Point {
	int x, y;
};

const int N = 1e6;

int n;

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;
}

namespace sub12 {
	const int sN = 16;
	
	bool vis[sN+5];
	
	bool check() {
		return n <= sN;
	}
	
	void solve() {
		for (int msk = 0; msk < (1<<n); msk++) {
			for (auto x : dx) cntx[x] = 0;
			for (auto y : dy) cnty[y] = 0;
			
			fill(ans+1, ans+n+1, 0);
			
			for (int i = 0; i < n; i++) {
				if ((msk>>i)&1) on(i+1);
			}
			
			bool check = 1;
			
			for (auto x : dx) {
				check &= cntx[x] <= 2;
			}
			
			for (auto y : dy) {
				check &= cnty[y] <= 2;
			}
			
			if (!check) continue;
			
			fill(vis+1, vis+n+1, 0);
			
			for (auto x : dx) {
				int lf = -1, rt = -1;
				
				for (int i = 0; i < X[x].size() && lf < 0; i++) {
					if (ans[X[x][i]]) lf = i;
				}
				
				for (int i = X[x].size()-1; i >= 0 && rt < 0; i--) {
					if (ans[X[x][i]]) rt = i;
				}
					
				if (lf == -1) continue;
				
				for (int i = lf; i <= rt; i++) vis[X[x][i]] = 1;
			}
			
			for (auto y : dy) {
				int lf = -1, rt = -1;
				
				for (int i = 0; i < Y[y].size() && lf < 0; i++) {
					if (ans[Y[y][i]]) lf = i;
				}
				
				for (int i = Y[y].size()-1; i >= 0 && rt < 0; i--) {
					if (ans[Y[y][i]]) rt = i;
				}
				
				if (lf == -1) continue;
				
				for (int i = lf; i <= rt; i++) vis[Y[y][i]] = 1;
			}
			
			for (int i = 1; i <= n; i++) {
				check &= vis[i];
			}
			
			if (!check) continue;
			
			break;
		}
	}
}

namespace sub3456 {	
	void solve() {
		for (auto x : dx) {
			on(X[x][0]), on(X[x].back());
		}
		
		for (auto y : dy) {
			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]);
				}
			}
		}
	}
}

void flo(int ID) {
	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);
	}
	
	for (auto y : dy) {
		sort(Y[y].begin(), Y[y].end(), cmpx);
	}
	
	if (sub12::check()) sub12::solve();
	else sub3456::solve();
	
	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;
}

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

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

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