# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
1061370 | seoul_korea | Naval battle (CEOI24_battle) | C++17 | 1258 ms | 1048576 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
// Goten2308
#include<bits/stdc++.h>
using namespace std;
#define int long long
using ll = long long;
using ii = pair <int, int>;
#define fi first
#define se second
#define mp(x, y) make_pair(x, y)
#define pb(x) push_back(x)
#define all(x) (x).begin(), (x).end()
#define endl '\n'
#define BIT(x, y) ((x >> y) & 1)
#define MASK(x) (1 << x)
#define MOD 1000000007
#define MULTI_TEST1
#define __GOTEN_WILL_BE_BETTER__ signed main()
template <class T> bool maximize(T& a, T b) { if(a < b) { a = b; return true; } return false; }
template <class T> bool minimize(T& a, T b) { if(a > b) { a = b; return true; } return false; }
template <class T> void add(T& a, T b) { a += b; if(a >= MOD) a -= MOD; }
template <class T> void sub(T& a, T b) { a -= b; if(a < 0) a += MOD; }
const int maxN = (int)2e5 + 7;
struct Event{
int fr, to, at;
Event() {
fr = 0, to = 0, at = 0;
}
Event(int _fr, int _to, int _at) {
fr = _fr;
to = _to;
at = _at;
}
};
bool cmp(Event a, Event b) {
return a.at < b.at;
}
struct Board{
int x, y;
char type;
} a[maxN];
vector<int> store[5];
int n;
int enc(char x) {
if(x == 'S') return 0;
if(x == 'N') return 1;
if(x == 'E') return 2;
if(x == 'W') return 3;
}
int calcTime(Board a, Board b) {
if(enc(a.type) > enc(b.type)) swap(a, b);
if(enc(a.type) == 0) {
if(enc(b.type) == 1) {
if(a.x > b.x || a.y != b.y || (a.x + b.x & 1)) return -1;
return (a.x + b.x >> 1) - a.x;
}
if(enc(b.type) == 2) {
if(b.x - a.x == a.y - b.y && a.y - b.y >= 0) return a.y - b.y;
return -1;
}
if(enc(b.type) == 3) {
if(b.x - a.x == b.y - a.y && b.y - a.y >= 0) return b.y - a.y;
return -1;
}
}
if(enc(a.type) == 1) {
if(enc(b.type) == 2) {
if(a.x - b.x == a.y - b.y && a.y - b.y >= 0) return a.y - b.y;
return -1;
}
if(enc(b.type) == 3) {
if(a.x - b.x == b.y - a.y && b.y - a.y >= 0) return b.y - a.y;
return -1;
}
}
if(enc(a.type) == 2) {
if(enc(b.type) == 3) {
if((a.y + b.y & 1) || a.x != b.x || a.y > b.y) return -1;
return (a.y + b.y >> 1) - a.y;
}
}
}
pair<int, int> midPos(Event e) {
Board cur = a[e.fr], other = a[e.to];
if(enc(cur.type) > enc(other.type)) swap(cur, other);
if(enc(cur.type) == 0) {
if(enc(other.type) == 1) {
return make_pair(cur.x + other.x >> 1, cur.y);
}
if(enc(other.type) == 2) {
return make_pair(other.x, cur.y);
}
if(enc(other.type) == 3) {
return make_pair(other.x, cur.y);
}
}
if(enc(cur.type) == 1) {
if(enc(other.type) == 2) {
return make_pair(other.x, cur.y);
}
if(enc(other.type) == 3) {
return make_pair(other.x, cur.y);
}
}
if(enc(cur.type) == 2) {
if(enc(other.type) == 3) {
return make_pair(cur.x, cur.y + other.y >> 1);
}
}
}
void solve() {
cin >> n;
for(int i = 1; i <= n; i++) {
cin >> a[i].y >> a[i].x >> a[i].type;
store[enc(a[i].type)].pb(i);
}
vector<Event> timeline;
for(int i = 1; i <= n; i++) {
for(int nxt = 0; nxt <= 3; nxt++) {
if(nxt == enc(a[i].type)) continue;
for(auto j : store[nxt]) {
if(i > j) continue;
int k = calcTime(a[i], a[j]);
if(k == -1) continue;
timeline.push_back(Event(i, j, k));
}
}
}
sort(all(timeline), cmp);
vector<bool> isAlive(n + 1, 1);
Event last = Event();
for(auto sukien : timeline) {
if(isAlive[sukien.fr] && isAlive[sukien.to] || (sukien.at == last.at && midPos(last) == midPos(sukien) )) {
isAlive[sukien.fr] = 0;
isAlive[sukien.to] = 0;
}
last = sukien;
// cout << sukien.fr << ' ' << sukien.to << ' ' << sukien.at << endl;
}
for(int i = 1; i <= n; i++) if(isAlive[i]) cout << i << endl;
}
__GOTEN_WILL_BE_BETTER__ {
#define task ""
if(fopen(task".inp", "r")){
freopen(task".inp", "r", stdin);
freopen(task".out", "w", stdout);
}
if(fopen("task.inp", "r")){
freopen("task.inp", "r", stdin);
freopen("task.out", "w", stdout);
}
cin.tie(0)->ios_base::sync_with_stdio(0);
int nTest = 1;
#ifdef MULTI_TEST
cin >> nTest;
#endif
while(nTest--) {
solve();
}
cout << endl;
return 0;
}
컴파일 시 표준 에러 (stderr) 메시지
# | 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... |