oj.uz

답안 #886594

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
886594 2023-12-12T11:13:36 Z vjudge1 Towers (NOI22_towers) C++17
12 / 100
 2000 ms 188680 KB 
#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

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

Subtask #1
5.0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 37468 KB Output is correct
2 Correct 5 ms 37720 KB Output is correct
3 Correct 5 ms 37468 KB Output is correct
4 Correct 5 ms 37468 KB Output is correct
5 Correct 5 ms 37468 KB Output is correct
6 Correct 5 ms 37468 KB Output is correct
7 Correct 5 ms 37468 KB Output is correct
8 Correct 5 ms 37468 KB Output is correct
9 Correct 6 ms 37468 KB Output is correct
10 Correct 5 ms 37468 KB Output is correct

Subtask #2
0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 37468 KB Output is correct
2 Correct 5 ms 37720 KB Output is correct
3 Correct 5 ms 37468 KB Output is correct
4 Correct 5 ms 37468 KB Output is correct
5 Correct 5 ms 37468 KB Output is correct
6 Correct 5 ms 37468 KB Output is correct
7 Correct 5 ms 37468 KB Output is correct
8 Correct 5 ms 37468 KB Output is correct
9 Correct 6 ms 37468 KB Output is correct
10 Correct 5 ms 37468 KB Output is correct
11 Incorrect 5 ms 37464 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #3
7.0 / 7.0

# 결과 실행 시간 메모리 Grader output
1 Correct 76 ms 53840 KB Output is correct
2 Correct 91 ms 56400 KB Output is correct
3 Correct 468 ms 91344 KB Output is correct
4 Correct 861 ms 143300 KB Output is correct
5 Correct 113 ms 57784 KB Output is correct
6 Correct 27 ms 42840 KB Output is correct
7 Correct 615 ms 138064 KB Output is correct
8 Correct 464 ms 103764 KB Output is correct
9 Correct 967 ms 179696 KB Output is correct
10 Correct 783 ms 159620 KB Output is correct
11 Correct 1334 ms 188680 KB Output is correct
12 Correct 1291 ms 188340 KB Output is correct

Subtask #4
0 / 6.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 2098 ms 187460 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 31.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 37468 KB Output is correct
2 Correct 5 ms 37720 KB Output is correct
3 Correct 5 ms 37468 KB Output is correct
4 Correct 5 ms 37468 KB Output is correct
5 Correct 5 ms 37468 KB Output is correct
6 Correct 5 ms 37468 KB Output is correct
7 Correct 5 ms 37468 KB Output is correct
8 Correct 5 ms 37468 KB Output is correct
9 Correct 6 ms 37468 KB Output is correct
10 Correct 5 ms 37468 KB Output is correct
11 Incorrect 5 ms 37464 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #6
0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 37468 KB Output is correct
2 Correct 5 ms 37720 KB Output is correct
3 Correct 5 ms 37468 KB Output is correct
4 Correct 5 ms 37468 KB Output is correct
5 Correct 5 ms 37468 KB Output is correct
6 Correct 5 ms 37468 KB Output is correct
7 Correct 5 ms 37468 KB Output is correct
8 Correct 5 ms 37468 KB Output is correct
9 Correct 6 ms 37468 KB Output is correct
10 Correct 5 ms 37468 KB Output is correct
11 Incorrect 5 ms 37464 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #7
0 / 19.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 37468 KB Output is correct
2 Correct 5 ms 37720 KB Output is correct
3 Correct 5 ms 37468 KB Output is correct
4 Correct 5 ms 37468 KB Output is correct
5 Correct 5 ms 37468 KB Output is correct
6 Correct 5 ms 37468 KB Output is correct
7 Correct 5 ms 37468 KB Output is correct
8 Correct 5 ms 37468 KB Output is correct
9 Correct 6 ms 37468 KB Output is correct
10 Correct 5 ms 37468 KB Output is correct
11 Incorrect 5 ms 37464 KB Output isn't correct
12 Halted 0 ms 0 KB -