#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int MOD = 1e9 + 7;
const int INF = 1e9;
const int MAX_N = 1e5 + 5;
void solve() {
int n; cin >> n;
int x[n],y[n];
char d[n];
for(int i=0; i<n; i++) {
cin >> x[i] >> y[i] >> d[i];
}
if(n <= 5000) {
vector<vector<ll>> sudar(n+1, vector<ll>(n+1, 1e18));
for(int i=0; i<n; i++) {
for(int j=0; j<n; j++) {
if(d[i] == d[j]) {
continue;
}
if(d[i] == 'S') {
if(d[j] == 'N') {
if(x[i] == x[j] and y[i] < y[j]) {
sudar[i][j] = (y[j]-y[i]) / 2;
}
} else if(d[j] == 'E') {
if(x[i] + y[i] == x[j] + y[j] and y[i] < y[j]) {
sudar[i][j] = y[j] - y[i];
}
} else if(d[j] == 'W') {
if(x[i] - y[i] == x[j] - y[j] and y[i] < y[j]) {
sudar[i][j] = y[j] - y[i];
}
}
}
else if(d[i] == 'N') {
if(d[j] == 'E') {
if(x[i] - y[i] == x[j] - y[j] and y[i] > y[j]) {
sudar[i][j] = y[i] - y[j];
}
} else if(d[j] == 'W') {
if(x[i] + y[i] == x[j] + y[j] and y[i] > y[j]) {
sudar[i][j] = y[i] - y[j];
}
}
}
else if(d[i] == 'E') {
if(d[j] == 'W') {
if(y[i] == y[j] and x[i] < x[j]) {
sudar[i][j] = (x[j]-x[i]) / 2;
}
}
}
}
}
vector<pair<ll,pair<int,int>>>v;
for(int i=0; i<n; i++) {
for(int j=0; j<n; j++) {
if(sudar[i][j] != 1e18) {
v.push_back({sudar[i][j], {i,j}});
}
}
}
sort(v.begin(), v.end());
vector<int>blown(n+1,0);
for(auto x : v) {
//cout << x.first << " " << x.second.first << " " << x.second.second << endl;
if(blown[x.second.first] > 0 and blown[x.second.first] != x.first or blown[x.second.second] > 0 and blown[x.second.second] != x.first) continue;
blown[x.second.first] = x.first;
blown[x.second.second] = x.first;
}
for(int i=0; i<n; i++) {
if(!blown[i]) cout << i+1 << endl;
}
} else {
vector<int> ans;
vector<vector<pair<int,int>>>v(n);
map<ll, int> m;
int tren=1;
for(int i=0; i<n; i++) {
ll sum = x[i] + y[i];
if(!m[sum]) {
m[sum] = tren;
tren++;
}
v[m[sum]-1].push_back({y[i], i});
}
for(int i=0; i<tren; i++) {
stack<int>s;
sort(v[i].begin(), v[i].end());
for(auto x : v[i]) {
if(d[x.second] == 'S') {
s.push(x.second);
continue;
}
if(s.empty()) ans.push_back(x.second);
else s.pop();
}
while(!s.empty()) {
int cur = s.top();
s.pop();
ans.push_back(cur);
}
}
for(auto x : ans) cout << x+1 << endl;
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(NULL); cout.tie(NULL);
//freopen("input.txt", "r", stdin);
//freopen("output.txt", "w", stdout);
int tc=1;
while(tc--)
solve();
}
# | 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... |