oj.uz

Submission #886575

# Submission time Handle Problem Language Result Execution time Memory
886575 2023-12-12T10:34:19 Z vjudge1 Towers (NOI22_towers) C++17
5 / 100
 2000 ms 186764 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 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.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 37476 KB Output is correct
2 Correct 5 ms 37468 KB Output is correct
3 Correct 6 ms 37468 KB Output is correct
4 Correct 6 ms 37468 KB Output is correct
5 Correct 5 ms 37720 KB Output is correct
6 Correct 6 ms 37464 KB Output is correct
7 Correct 5 ms 37340 KB Output is correct
8 Correct 5 ms 37468 KB Output is correct
9 Correct 7 ms 37468 KB Output is correct
10 Correct 6 ms 37468 KB Output is correct

Subtask #2
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 37476 KB Output is correct
2 Correct 5 ms 37468 KB Output is correct
3 Correct 6 ms 37468 KB Output is correct
4 Correct 6 ms 37468 KB Output is correct
5 Correct 5 ms 37720 KB Output is correct
6 Correct 6 ms 37464 KB Output is correct
7 Correct 5 ms 37340 KB Output is correct
8 Correct 5 ms 37468 KB Output is correct
9 Correct 7 ms 37468 KB Output is correct
10 Correct 6 ms 37468 KB Output is correct
11 Incorrect 5 ms 37468 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #3
0 / 7.0

# Verdict Execution time Memory Grader output
1 Incorrect 76 ms 53828 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 6.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2017 ms 186764 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 31.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 37476 KB Output is correct
2 Correct 5 ms 37468 KB Output is correct
3 Correct 6 ms 37468 KB Output is correct
4 Correct 6 ms 37468 KB Output is correct
5 Correct 5 ms 37720 KB Output is correct
6 Correct 6 ms 37464 KB Output is correct
7 Correct 5 ms 37340 KB Output is correct
8 Correct 5 ms 37468 KB Output is correct
9 Correct 7 ms 37468 KB Output is correct
10 Correct 6 ms 37468 KB Output is correct
11 Incorrect 5 ms 37468 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #6
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 37476 KB Output is correct
2 Correct 5 ms 37468 KB Output is correct
3 Correct 6 ms 37468 KB Output is correct
4 Correct 6 ms 37468 KB Output is correct
5 Correct 5 ms 37720 KB Output is correct
6 Correct 6 ms 37464 KB Output is correct
7 Correct 5 ms 37340 KB Output is correct
8 Correct 5 ms 37468 KB Output is correct
9 Correct 7 ms 37468 KB Output is correct
10 Correct 6 ms 37468 KB Output is correct
11 Incorrect 5 ms 37468 KB Output isn't correct
12 Halted 0 ms 0 KB -

Subtask #7
0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 37476 KB Output is correct
2 Correct 5 ms 37468 KB Output is correct
3 Correct 6 ms 37468 KB Output is correct
4 Correct 6 ms 37468 KB Output is correct
5 Correct 5 ms 37720 KB Output is correct
6 Correct 6 ms 37464 KB Output is correct
7 Correct 5 ms 37340 KB Output is correct
8 Correct 5 ms 37468 KB Output is correct
9 Correct 7 ms 37468 KB Output is correct
10 Correct 6 ms 37468 KB Output is correct
11 Incorrect 5 ms 37468 KB Output isn't correct
12 Halted 0 ms 0 KB -