Submission #886595

#	Time	Username	Problem	Language	Result	Execution time	Memory
886595		vjudge1	Towers (NOI22_towers)	C++17	5 / 100	2051 ms	179908 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 erase = [&](int ind){
		hor.erase({Y[ind], X[ind], ind});
		ver.erase({X[ind], Y[ind], ind});
	};

	auto taken = [&](array<int, 3> p, int t){
		if (t == 2) swap(p[0], p[1]);
		if ((colmin[p[0]] > p[1] || colmax[p[0]] < p[1]) && 
				(rowmin[p[1]] > p[0] || rowmax[p[1]] < p[0])){
			ans[p[2]] = 1;
			//cout<<p[2]<<" :"<<rowmin[p[1]]<<sp<<rowmax[p[1]]<<sp<<p[0]<<endl;
			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]);
		}
		erase(p[2]);
	};


	vector<array<int, 3>> corner;
	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){
			corner.pb(a);
		}
		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];
			erase(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++;
			}
			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);
		}
		if (corner.size() == 1){
			taken(corner.front(), t);
		}
		else if (corner.size() == 2) {
			array<int, 3> a = corner.front(), b = corner.back();
			if (a[1] == b[1]){
				vector<array<int, 3>> gh;
				gh.pb({a[1], a[0], a[2]});
				gh.pb({b[1], b[0], b[2]});
				clear(gh, 3 - t);
			} 
			else taken(a, t), taken(b, t);
		}
		corner.clear();
	};
	int steps = 0;
	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";
}

Compilation message (stderr)

Main.cpp: In function 'int32_t main()':
Main.cpp:125:6: warning: unused variable 'steps' [-Wunused-variable]
  125 |  int steps = 0;
      |      ^~~~~

• 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