Submission #831198

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
831198	2023-08-19T21:58:02 Z	NK_	Towers (NOI22_towers)	C++17	12 / 100	2000 ms	186640 KB

Main

// Success consists of going from failure to failure without loss of enthusiasm
#include <bits/stdc++.h>

using namespace std;
 
#define nl '\n'
#define pb push_back
#define mp make_pair
#define f first
#define s second
#define sz(x) int(x.size())
 
template<class T> using V = vector<T>;
using pi = pair<int, int>;
using vi = V<int>;
using vpi = V<pi>;

using ll = long long;
using pl = pair<ll, ll>;
using vpl = V<pl>;
using vl = V<ll>;

using db = long double;

template<class T> using pq = priority_queue<T, V<T>, greater<T>>;

const int MOD = 1e9 + 7;
const ll INFL = ll(1e16) + 10;

int main() {
	cin.tie(0)->sync_with_stdio(0);
	
	int N; cin >> N;
	vpi A(N); for(auto& x : A) cin >> x.f >> x.s;


	for(int t = 0; t < 2; t++) {
		map<int, int> mp; int cur = 0;
		for(auto& x : A) mp[x.f]++;
		for(auto& x : mp) x.s = cur++;
		for(auto& x : A) x.f = mp[x.f], swap(x.f, x.s);
	}

	map<pi, int> IDX; for(int i = 0; i < N; i++) {
		// cerr << A[i].f << " " << A[i].s << " is " << i << endl;
		IDX[A[i]] = i;
	}

	V<vi> C(N);
	for(int i = 0; i < N; i++) C[A[i].s].pb(A[i].f);

	for(int i = 0; i < N; i++) sort(begin(C[i]), end(C[i]));

	V<vpi> R(N); 

	vi POS(2 * N, -1);
	function<void(int)> update = [&](int x) {
		// cout << "UPDATE " << x << endl;
		if (POS[x] == -1) return;
		// 2*y+c => y is col # and c is dir (0 - dwn (+1), 1 - up (-1));
		while(1) {
			int y = x / 2, dir = (x % 2 ? -1 : +1);
			if (POS[x] < 0 || POS[x] >= sz(C[y])) {
				POS[x] = -1; return;
			}

			if (POS[2*y] == POS[2*y+1]) {
				POS[x] = -1;
				return; // stop because same as other one
			}

			int r = C[y][POS[x]]; // row
			// cerr << x << " " << y << " " << dir << " " << r << endl;

			// check if you can put it in
			if (sz(R[r]) <= 1) {
				// cerr << "ADDED TO " << r << endl;
				R[r].pb(mp(y, x)); return;
			} else if (R[r].back().f < y) { // sz(R[r]) == 2
				// cerr << "ADDED2 TO " << r << endl;
				// cerr << "MUST UPDATE: " << i << endl;
				int i = R[r].back().s; 
				R[r].pop_back(); R[r].pb(mp(y, x));
				return update(i);
			}	

			POS[x] += dir;
		}
	};

	vi cols; for(int i = 0; i < N; i++) {
		cols.pb(A[i].s);
	}

	sort(begin(cols), end(cols)); cols.erase(unique(begin(cols), end(cols)), end(cols));

	for(auto& c : cols) { 
		POS[2 * c] = 0; 
		update(2 * c); 

		POS[2 * c + 1] = sz(C[c]) - 1;
		update(2 * c + 1);
	}

	vpi take;
	for(int i = 0; i < 2 * N; i++) {
		int c = i / 2; 
		if (0 <= POS[i] && POS[i] < sz(C[c])) {
			take.pb(mp(C[c][POS[i]], c));
			// cerr << i << " " << c << " " << C[c][POS[i]] << endl;
		}
	}

	string ans(N, '0');
	for(auto& p : take) ans[IDX[p]] = '1';

	cout << ans << nl;

    return 0;
}

Subtask #1
5.0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	212 KB	Output is correct
2	Correct	0 ms	212 KB	Output is correct
3	Correct	0 ms	212 KB	Output is correct
4	Correct	0 ms	212 KB	Output is correct
5	Correct	0 ms	212 KB	Output is correct
6	Correct	0 ms	212 KB	Output is correct
7	Correct	0 ms	212 KB	Output is correct
8	Correct	0 ms	212 KB	Output is correct
9	Correct	1 ms	288 KB	Output is correct
10	Correct	0 ms	212 KB	Output is correct

Subtask #2
0 / 11.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	212 KB	Output is correct
2	Correct	0 ms	212 KB	Output is correct
3	Correct	0 ms	212 KB	Output is correct
4	Correct	0 ms	212 KB	Output is correct
5	Correct	0 ms	212 KB	Output is correct
6	Correct	0 ms	212 KB	Output is correct
7	Correct	0 ms	212 KB	Output is correct
8	Correct	0 ms	212 KB	Output is correct
9	Correct	1 ms	288 KB	Output is correct
10	Correct	0 ms	212 KB	Output is correct
11	Correct	1 ms	212 KB	Output is correct
12	Correct	0 ms	212 KB	Output is correct
13	Correct	0 ms	212 KB	Output is correct
14	Correct	0 ms	212 KB	Output is correct
15	Correct	0 ms	212 KB	Output is correct
16	Correct	0 ms	212 KB	Output is correct
17	Incorrect	0 ms	212 KB	Output isn't correct
18	Halted	0 ms	0 KB	-

Subtask #3
7.0 / 7.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	37 ms	13860 KB	Output is correct
2	Correct	46 ms	16456 KB	Output is correct
3	Correct	140 ms	49356 KB	Output is correct
4	Correct	299 ms	96044 KB	Output is correct
5	Correct	46 ms	17772 KB	Output is correct
6	Correct	9 ms	3924 KB	Output is correct
7	Correct	299 ms	90780 KB	Output is correct
8	Correct	170 ms	60416 KB	Output is correct
9	Correct	457 ms	135756 KB	Output is correct
10	Correct	376 ms	112952 KB	Output is correct
11	Correct	477 ms	143160 KB	Output is correct
12	Correct	452 ms	143040 KB	Output is correct

Subtask #4
0 / 6.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1008 ms	153620 KB	Output is correct
2	Correct	1006 ms	153552 KB	Output is correct
3	Correct	1012 ms	153644 KB	Output is correct
4	Correct	1010 ms	153580 KB	Output is correct
5	Correct	1000 ms	153580 KB	Output is correct
6	Execution timed out	2033 ms	186640 KB	Time limit exceeded
7	Halted	0 ms	0 KB	-

Subtask #5
0 / 31.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	212 KB	Output is correct
2	Correct	0 ms	212 KB	Output is correct
3	Correct	0 ms	212 KB	Output is correct
4	Correct	0 ms	212 KB	Output is correct
5	Correct	0 ms	212 KB	Output is correct
6	Correct	0 ms	212 KB	Output is correct
7	Correct	0 ms	212 KB	Output is correct
8	Correct	0 ms	212 KB	Output is correct
9	Correct	1 ms	288 KB	Output is correct
10	Correct	0 ms	212 KB	Output is correct
11	Correct	1 ms	212 KB	Output is correct
12	Correct	0 ms	212 KB	Output is correct
13	Correct	0 ms	212 KB	Output is correct
14	Correct	0 ms	212 KB	Output is correct
15	Correct	0 ms	212 KB	Output is correct
16	Correct	0 ms	212 KB	Output is correct
17	Incorrect	0 ms	212 KB	Output isn't correct
18	Halted	0 ms	0 KB	-

Subtask #6
0 / 21.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	212 KB	Output is correct
2	Correct	0 ms	212 KB	Output is correct
3	Correct	0 ms	212 KB	Output is correct
4	Correct	0 ms	212 KB	Output is correct
5	Correct	0 ms	212 KB	Output is correct
6	Correct	0 ms	212 KB	Output is correct
7	Correct	0 ms	212 KB	Output is correct
8	Correct	0 ms	212 KB	Output is correct
9	Correct	1 ms	288 KB	Output is correct
10	Correct	0 ms	212 KB	Output is correct
11	Correct	1 ms	212 KB	Output is correct
12	Correct	0 ms	212 KB	Output is correct
13	Correct	0 ms	212 KB	Output is correct
14	Correct	0 ms	212 KB	Output is correct
15	Correct	0 ms	212 KB	Output is correct
16	Correct	0 ms	212 KB	Output is correct
17	Incorrect	0 ms	212 KB	Output isn't correct
18	Halted	0 ms	0 KB	-

Subtask #7
0 / 19.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	212 KB	Output is correct
2	Correct	0 ms	212 KB	Output is correct
3	Correct	0 ms	212 KB	Output is correct
4	Correct	0 ms	212 KB	Output is correct
5	Correct	0 ms	212 KB	Output is correct
6	Correct	0 ms	212 KB	Output is correct
7	Correct	0 ms	212 KB	Output is correct
8	Correct	0 ms	212 KB	Output is correct
9	Correct	1 ms	288 KB	Output is correct
10	Correct	0 ms	212 KB	Output is correct
11	Correct	1 ms	212 KB	Output is correct
12	Correct	0 ms	212 KB	Output is correct
13	Correct	0 ms	212 KB	Output is correct
14	Correct	0 ms	212 KB	Output is correct
15	Correct	0 ms	212 KB	Output is correct
16	Correct	0 ms	212 KB	Output is correct
17	Incorrect	0 ms	212 KB	Output isn't correct
18	Halted	0 ms	0 KB	-

Submission #831198

Compilation message

Subtask #1 5.0 / 5.0

Subtask #2 0 / 11.0

Subtask #3 7.0 / 7.0

Subtask #4 0 / 6.0

Subtask #5 0 / 31.0

Subtask #6 0 / 21.0

Subtask #7 0 / 19.0

Subtask #1
5.0 / 5.0

Subtask #2
0 / 11.0

Subtask #3
7.0 / 7.0

Subtask #4
0 / 6.0

Subtask #5
0 / 31.0

Subtask #6
0 / 21.0

Subtask #7
0 / 19.0