QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#22645 | #2365. Flight Collision | Suzt_ilymtics# | WA | 3ms | 3720kb | C++14 | 2.2kb | 2022-03-10 14:40:41 | 2022-04-30 01:29:13 |
Judging History
answer
#include<bits/stdc++.h>
#define LL long long
#define int long long
#define orz cout << "tyy YYDS!\n"
using namespace std;
const int MAXN = 2e5 + 10;
const int mod = 998244353;
struct node {
int id, x, pre, nxt, v;
}a[MAXN];
struct Node {
double tim;
int x, y;
bool operator < (const Node &b) const { return tim == b.tim ? x == b.x ? y < b.y : x < b.x : tim < b.tim; }
};
int n;
set<Node> S;
bool vis[MAXN];
int read() {
int s = 0, f = 0;
char ch = getchar();
while(!isdigit(ch)) f |= (ch == '-'), ch = getchar();
while(isdigit(ch)) s = (s << 1) + (s << 3) + (ch ^ 48), ch = getchar();
return f ? -s : s;
}
bool Check(int x, int y) {
if(a[x].v > 0 && a[y].v < 0) return true;
if(a[x].v > 0 && a[y].v > 0 && a[x].v > a[y].v) return true;
if(a[x].v < 0 && a[y].v < 0 && a[x].v > a[y].v) return true;
return false;
}
signed main() {
n = read();
for(int i = 1; i <= n; ++i) {
a[i].id = i;
a[i].x = read();
a[i].pre = i - 1;
a[a[i].pre].nxt = i;
a[i].v = read();
}
a[1].pre = 0;
a[n].nxt = n + 1;
for(int i = 1; i < n; ++i) {
if(Check(i, i + 1)) {
// double res = 1.0 * (a[i + 1].x - a[i].x) / (a[i].v - a[i + 1].v);
// cout << "add: " << i << " " << i + 1 << " " << res << "\n";
S.insert((Node){1.0 * (a[i + 1].x - a[i].x) / (a[i].v - a[i + 1].v), i, i + 1});
}
}
while(!S.empty()) {
Node u = *S.begin(); S.erase(*S.begin());
// cout << u.x << " " << u.y << "\n";
if(vis[u.x] || vis[u.y]) continue;
vis[u.x] = vis[u.y] = true;
if(a[u.x].pre == 0 || a[u.y].nxt == n + 1) continue;
a[a[u.x].pre].nxt = a[u.y].nxt;
a[a[u.y].nxt].pre = a[u.x].pre;
if(Check(a[u.x].pre, a[u.y].nxt)) {
S.insert((Node){1.0 * (a[a[u.y].nxt].x - a[a[u.x].pre].x) / (a[a[u.x].pre].v - a[a[u.y].nxt].v), a[u.x].pre, a[u.y].nxt});
}
}
int ans = 0;
for(int i = 1; i <= n; ++i) ans += (!vis[i]);
printf("%lld\n", ans);
for(int i = 1; i <= n; ++i) if(!vis[i]) printf("%lld ", i);
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 3ms
memory: 3720kb
input:
1 -4 13
output:
1 1
result:
ok 2 lines
Test #2:
score: 0
Accepted
time: 3ms
memory: 3660kb
input:
5 1 1000000000 2 1000000000 3 -1000000000 4 -1000000000 5 -1000000000
output:
1 5
result:
ok 2 lines
Test #3:
score: -100
Wrong Answer
time: 3ms
memory: 3700kb
input:
3 -1000000000 1 999999999 0 1000000000 0
output:
3 1 2 3
result:
wrong answer 1st lines differ - expected: '1', found: '3'