Submission #886575

#	Time	Username	Problem	Language	Result	Execution time	Memory
886575		vjudge1	Towers (NOI22_towers)	C++17	5 / 100	2017 ms	186764 KiB

Main

#include <bits/stdc++.h>
using namespace std;
#define fileio() freopen("input.txt", "r", stdin), freopen("output.txt", "w", stdout)
#define fastio() cin.tie(0), ios_base::sync_with_stdio(0)
#define sp " "
#define endl "\n"
#define pb push_back
#define pii pair<int, int>
#define st first
#define nd second 
#define N 1000005
#define int long long

const int modulo = 1e9 + 7;

int ans[N], Y[N], X[N], colmax[N], colmin[N], rowmax[N], rowmin[N];

int32_t main()
{
	//fileio();
	fastio();

	int n;
	cin>>n;
	set<array<int, 3>> hor, ver;

	for (int i = 0; i < N; i++){
		rowmax[i] = colmax[i] = 0, rowmin[i] = colmin[i] = N;
	}

	for (int i = 1; i <= n; i++){
		cin>>X[i]>>Y[i];
		ver.insert({X[i], Y[i], i});
		hor.insert({Y[i], X[i], i});
	}

	auto taken = [&](array<int, 3> p, int t){
		ans[p[2]] = 1;
		if (t == 2) swap(p[0], p[1]);
		colmin[p[0]] = min(colmin[p[0]], p[1]);
		colmax[p[0]] = max(colmax[p[0]], p[1]);
		rowmin[p[1]] = min(rowmin[p[1]], p[0]);
		rowmax[p[1]] = max(rowmax[p[1]], p[0]);
	};

	auto clear = [&](vector<array<int, 3>> v, int t){
		array<int, 3> a = v.front(), b = v.back();
		if (a > b) swap(a, b);
		if (a == b){
			if ((colmin[a[0]] > a[1] || colmax[a[0]] < a[1]) && 
				(rowmin[a[0]] > a[1] || rowmax[a[0]] < a[1])) taken(a, t);
		}
		else{
			if (t == 1){ //vertical
				if (colmin[a[0]] > a[1]) taken(a, t);
				if (colmax[b[0]] < b[1]) taken(b, t);
			}
			else { //horizontal
				if (rowmin[a[0]] > a[1]) taken(a, t);
				if (rowmax[b[0]] < b[1]) taken(b, t);
			}	
		}
		for (auto i : v){
			int ind = i[2];
			hor.erase({Y[ind], X[ind], ind});
			ver.erase({X[ind], Y[ind], ind});
		}
	};

	

	auto take_off = [&](set<array<int, 3>> &s, int t){
		auto it = s.begin();
		if (it != s.end()){
			int last = (*it)[0];
			vector<array<int, 3>> v;
			v.pb(*it);
			it++;
			while(it != s.end() && (*it)[0] == last)
			{
				v.pb(*it);
				it++;
			}
			if (v.size() == 1) 
			clear(v, t);
		}

		auto it2 = s.rbegin();
		if (it2 != s.rend()){
			int last = (*it2)[0];
			vector<array<int, 3>> v;
			v.pb(*it2);
			it2++;
			while(it2 != s.rend() && (*it2)[0] == last)
			{
				v.pb(*it2);
				it2++;
			}
			clear(v, t);
		}
	};

	while(!ver.empty() && !hor.empty()){
		take_off(ver, 1);
		take_off(hor, 2);
	}


	for (int i = 1; i <= n; i++){
		cout<<ans[i];
	}
	cout<<endl;


	cerr << "time taken : " << (float)clock() / CLOCKS_PER_SEC << " seconds\n";
}

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