제출 #914659

#제출 시각아이디문제언어결과실행 시간메모리
914659davitmargTowers (NOI22_towers)C++17
18 / 100
827 ms125116 KiB
/* DavitMarg In a honky-tonk, Down in Mexico */ #define _CRT_SECURE_NO_WARNINGS #include <iostream> #include <algorithm> #include <cmath> #include <vector> #include <string> #include <cstring> #include <map> #include <unordered_map> #include <set> #include <unordered_set> #include <queue> #include <bitset> #include <stack> #include <cassert> #include <iterator> #include <random> #include <chrono> #define mod 998244353ll #define LL long long #define LD long double #define MP make_pair #define PB push_back #define all(v) v.begin(), v.end() #define fastIO ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); using namespace std; const int N = 1000006; #define X first.first #define Y first.second #define I second #define pt pair<pair<int,int>, int> int n, k; int ans[N]; pt p[N]; vector<pt> x[N], y[N]; int used_x_down[N], used_x_up[N]; void solve() { cin >> n; for (int i = 1; i <= n; i++) { cin >> p[i].X >> p[i].Y; k = max(k, max(p[i].X, p[i].Y)); p[i].I = i; y[p[i].Y].PB(p[i]); x[p[i].X].PB(p[i]); } for (int i = 1; i <= k; i++) { sort(all(x[i]), [](pt a, pt b) {return a.Y < b.Y; }); sort(all(y[i]), [](pt a, pt b) {return a.X < b.X; }); } int r = k; for (int l = 1; l <= r; l++) { int L, R; if(y[l].empty()) continue; while (r > l && y[r].empty()) r--; if (l == r) { L = 0; R = y[l].size() - 1; while (L < y[l].size() && used_x_down[y[l][L].X] && used_x_up[y[l][L].X]) L++; while (R >= 0 && used_x_down[y[l][R].X] && used_x_up[y[l][R].X]) R--; if (L <= R) { ans[y[l][L].I] = 1; ans[y[l][R].I] = 1; } break; } L = 0; R = y[l].size() - 1; while(L < y[l].size() && used_x_down[y[l][L].X] && x[y[l][L].X].back() != y[l][L]) L++; while(R >= 0 && used_x_down[y[l][R].X] && x[y[l][R].X].back() != y[l][R]) R--; if (L <= R) { used_x_down[y[l][L].X] = 1; ans[y[l][L].I] = 1; used_x_down[y[l][R].X] = 1; ans[y[l][R].I] = 1; } L = 0; R = y[r].size() - 1; while(L < y[r].size() && used_x_up[y[r][L].X] && x[y[r][L].X][0] != y[r][L]) L++; while (R >= 0 && used_x_up[y[r][R].X] && x[y[r][R].X][0] != y[r][R]) R--; if (L <= R) { used_x_up[y[r][L].X] = 1; ans[y[r][L].I] = 1; used_x_up[y[r][R].X] = 1; ans[y[r][R].I] = 1; } r--; } for (int i = 1; i <= n; i++) cout << ans[i]; cout << endl; } int main() { fastIO; int T = 1; //cin >> T; while (T--) { solve(); } return 0; } /* 8 1 1 2 1 3 1 1 2 2 2 3 2 2 3 3 3 9 1 1 2 1 3 1 1 2 2 2 3 2 1 3 2 3 3 3 7 1 1 3 1 1 2 2 2 3 2 1 3 3 3 3 1 1 1 2 1 3 16 1 1 1 2 1 3 1 4 2 1 2 2 2 3 2 4 3 1 3 2 3 3 3 4 4 1 4 2 4 3 4 4 */

컴파일 시 표준 에러 (stderr) 메시지

Main.cpp: In function 'void solve()':
Main.cpp:79:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<std::pair<int, int>, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   79 |             while (L < y[l].size() && used_x_down[y[l][L].X] && used_x_up[y[l][L].X])
      |                    ~~^~~~~~~~~~~~~
Main.cpp:95:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<std::pair<int, int>, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   95 |         while(L < y[l].size() && used_x_down[y[l][L].X] && x[y[l][L].X].back() != y[l][L])
      |               ~~^~~~~~~~~~~~~
Main.cpp:112:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<std::pair<int, int>, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  112 |         while(L < y[r].size() && used_x_up[y[r][L].X] && x[y[r][L].X][0] != y[r][L])
      |               ~~^~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...