Submission #886599

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
886599	2023-12-12T11:44:09 Z	Kel_Mahmut	Towers (NOI22_towers)	C++17	0 / 100	1676 ms	169412 KB

Main

#include <bits/stdc++.h>
#define pb push_back
#define all(aa) aa.begin(), aa.end()
using namespace std;

constexpr int maxn = 1e6;

int main(){
	int n;
	cin >> n;
	vector<vector<int>> X_vals(maxn);
	map<pair<int, int>, int> index;
	vector<vector<pair<int, int>>> Y_act(maxn); // cord, type (1 if it is upper bound, -1 if lower bound)
	vector<int> vis(n);
	for(int i = 0; i < n; i++){
		int x, y;
		cin >> x >> y;
		--x, --y;
		index[{x, y}] = i;
		X_vals[x].pb(y);
	}
	for(int i = 0; i < maxn; i++){
		if(!X_vals[i].empty())
			sort(all(X_vals[i]));
	}

	function<void(int)> fix = [&](int y){
		if(Y_act[y].size() <= 2){
			return;
		}
		// ayni y-de 3 tane nokta var
		sort(all(Y_act[y]));
		swap(Y_act[y][2], Y_act[y][1]);
		array<int, 3> to_fix = {Y_act[y][2].first, y, Y_act[y][2].second};
		Y_act[y].resize(2);
		vis[   index[{to_fix[0], to_fix[1]}]   ] = 0;
		if(to_fix[2] == 1){
			int y_nxt = (lower_bound(all(X_vals[to_fix[0]] ), to_fix[1])  - X_vals[to_fix[0]].begin() ) - 1;
			
			if(y_nxt < 0) 
				return;

			if(vis[  index[{to_fix[0], y_nxt}]  ])
				return;

			vis[  index[{to_fix[0], y_nxt}]  ] = 1;
			Y_act[  y_nxt ].pb({to_fix[0], 1});

			fix(y_nxt);
		}

		if(to_fix[2] == -1){
			int y_nxt = (lower_bound(all(X_vals[to_fix[0]] ), to_fix[1])  - X_vals[to_fix[0]].begin() ) + 1;
			
			if(y_nxt >= X_vals[to_fix[0]].size())
				return;

			if(vis[  index[{to_fix[0], y_nxt}]  ])
				return;

			vis[  index[{to_fix[0], y_nxt}]  ] = 1;
			Y_act[  y_nxt ].pb({to_fix[0], -1});

			fix(y_nxt);
		}
	};

	for(int i = 0; i < maxn; i++){
		if(X_vals[i].empty()) continue;	

		vector<int> x_col = X_vals[i];

		
		vis[  index[{i, x_col[0]}]  ] = 1;
		vis[  index[{i, x_col.back()}]  ] = 1;
		// cout << index[{i, x_col[0]}] << ' ' << index[{i, x_col.back()}] << endl;
		
		Y_act[x_col[0]].pb({i, -1});
		Y_act[x_col.back()].pb({i, 1});

		sort(all(Y_act[x_col[0]]));
		sort(all(Y_act[x_col.back()]));

		fix(x_col[0]);
		fix(x_col.back());

	}

	for(int i = 0; i < n; i++){
		cout << (vis[i] ? 1 : 0);
	}
}

Compilation message

Main.cpp: In lambda function:
Main.cpp:55:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   55 |    if(y_nxt >= X_vals[to_fix[0]].size())
      |       ~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1

0 / 5.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	16 ms	47192 KB	Output is correct
2	Correct	16 ms	47420 KB	Output is correct
3	Correct	15 ms	47348 KB	Output is correct
4	Correct	18 ms	47196 KB	Output is correct
5	Correct	16 ms	47196 KB	Output is correct
6	Correct	16 ms	47192 KB	Output is correct
7	Correct	16 ms	47452 KB	Output is correct
8	Incorrect	16 ms	47196 KB	Output isn't correct
9	Halted	0 ms	0 KB	-

Subtask #2

0 / 11.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	16 ms	47192 KB	Output is correct
2	Correct	16 ms	47420 KB	Output is correct
3	Correct	15 ms	47348 KB	Output is correct
4	Correct	18 ms	47196 KB	Output is correct
5	Correct	16 ms	47196 KB	Output is correct
6	Correct	16 ms	47192 KB	Output is correct
7	Correct	16 ms	47452 KB	Output is correct
8	Incorrect	16 ms	47196 KB	Output isn't correct
9	Halted	0 ms	0 KB	-

Subtask #3

0 / 7.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	64 ms	54096 KB	Output is correct
2	Correct	75 ms	55636 KB	Output is correct
3	Incorrect	337 ms	72096 KB	Output isn't correct
4	Halted	0 ms	0 KB	-

Subtask #4

0 / 6.0

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

Subtask #5

0 / 31.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	16 ms	47192 KB	Output is correct
2	Correct	16 ms	47420 KB	Output is correct
3	Correct	15 ms	47348 KB	Output is correct
4	Correct	18 ms	47196 KB	Output is correct
5	Correct	16 ms	47196 KB	Output is correct
6	Correct	16 ms	47192 KB	Output is correct
7	Correct	16 ms	47452 KB	Output is correct
8	Incorrect	16 ms	47196 KB	Output isn't correct
9	Halted	0 ms	0 KB	-

Subtask #6

0 / 21.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	16 ms	47192 KB	Output is correct
2	Correct	16 ms	47420 KB	Output is correct
3	Correct	15 ms	47348 KB	Output is correct
4	Correct	18 ms	47196 KB	Output is correct
5	Correct	16 ms	47196 KB	Output is correct
6	Correct	16 ms	47192 KB	Output is correct
7	Correct	16 ms	47452 KB	Output is correct
8	Incorrect	16 ms	47196 KB	Output isn't correct
9	Halted	0 ms	0 KB	-

Subtask #7

0 / 19.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	16 ms	47192 KB	Output is correct
2	Correct	16 ms	47420 KB	Output is correct
3	Correct	15 ms	47348 KB	Output is correct
4	Correct	18 ms	47196 KB	Output is correct
5	Correct	16 ms	47196 KB	Output is correct
6	Correct	16 ms	47192 KB	Output is correct
7	Correct	16 ms	47452 KB	Output is correct
8	Incorrect	16 ms	47196 KB	Output isn't correct
9	Halted	0 ms	0 KB	-