이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
#define sz(x) ((int)x.size())
#define all(x) x.begin(), x.end()
#define int long long
/*
using u32 = unsigned int;
using i64 = long long;
using u64 = unsigned long long;*/
using namespace std;
const int N = 2e5 + 42, T = 18, INF = 1e9 + 42;
struct Point {
int x, y, i, type;
};
//NSEW
int dl[] = {0, 0, 1, -1},
dc[] = {-1, 1, 0, 0};
int dirl[] = {-2, -1, 0, 1, 2, 1, 0, -1},
dirc[] = {0, 1, 2, 1, 0, -1, -2, -1};
Point pt[N];
bool mort[N];
int nxt[N][8][4];
struct Pair {
int i, j, dist;
bool operator <(const Pair& other) const {
return dist > other.dist;
}
};
priority_queue<Pair> pq;
void create(int a, int b) {
if(a != -1 && b != -1 && !mort[a] && !mort[b]) {
Point p = pt[a], q = pt[b];
int dist = (abs(p.x - q.x) + abs(p.y - q.y))/2;
if(p.x + dist * dl[p.type] == q.x + dist * dl[q.type] && p.y + dist * dc[p.type] == q.y + dist * dc[q.type]) {
pq.push({a, b, dist});
}
}
}
void del(int i) {
mort[i] = true;
int type = pt[i].type;
for(int iDir = 0; iDir < 8; iDir++) {
for(int t = 0; t < 4; t++) if(nxt[i][iDir][t] != -1) {
nxt[nxt[i][iDir][t]][(iDir + 4) & 7][type] = nxt[i][(iDir + 4) & 7][type];
int a = nxt[i][iDir][t], b = nxt[i][(iDir + 4) & 7][type];
create(a, b);
}
}
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(0);
int n; cin >> n;
map<char, int> cor;
cor['N'] = 0, cor['S'] = 1, cor['E'] = 2, cor['W'] = 3;
for(int i = 0; i < n; i++) {
pt[i].i = i;
cin >> pt[i].x >> pt[i].y;
char c; cin >> c;
pt[i].type = cor[c];
}
vector<pair<int, int>> pot;
for(int iDir = 0; iDir < 8; iDir++) {
sort(pt, pt + n,
[=](Point a, Point b) {
return a.x * dirc[iDir] - a.y * dirl[iDir] < b.x * dirc[iDir] - b.y * dirl[iDir];
});
map<int, int> pre[4];
for(int i = 0; i < n; i++) {
int proj = pt[i].x * dirl[iDir] + pt[i].y * dirc[iDir];
for(int t = 0; t < 4; t++) {
if(pre[t].count(proj)) {
nxt[pt[i].i][iDir][t] = pre[t][proj];
pot.push_back({pt[i].i, nxt[pt[i].i][iDir][t]});
} else {
nxt[pt[i].i][iDir][t] = -1;
}
}
pre[pt[i].type][proj] = pt[i].i;
}
}
sort(pt, pt + n,
[](Point a, Point b) {
return a.i < b.i;
});
for(auto [a, b] : pot) create(a, b);
while(!pq.empty()) {
int dist = pq.top().dist;
vector<int> suppr;
while(!pq.empty() && pq.top().dist == dist) {
int a = pq.top().i, b = pq.top().j;
if(!mort[a] && !mort[b]) {
suppr.push_back(a);
suppr.push_back(b);
}
pq.pop();
}
for(int i : suppr)
if(!mort[i])
del(i);
}
for(int i = 0; i < n; i++)
if(!mort[i]) cout << i+1 << '\n';
}
컴파일 시 표준 에러 (stderr) 메시지
Main.cpp: In function 'int main()':
Main.cpp:97:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
97 | for(auto [a, b] : pot) create(a, b);
| ^
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |