QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#22791 | #2365. Flight Collision | Suzt_ilymtics# | WA | 3ms | 5764kb | C++14 | 2.2kb | 2022-03-10 16:37:32 | 2022-04-30 01:40:39 |
Judging History
answer
#include<bits/stdc++.h>
#define LL long long
#define int long long
//#define double long double
#define orz cout << "tyy YYDS!\n"
using namespace std;
const int MAXN = 2e5 + 10;
const int mod = 998244353;
const long double eps = 1e-17;
struct node {
int id, x, pre, nxt, v;
}a[MAXN];
struct Node {
long double tim;
int x, y;
bool operator < (const Node &b) const {
if(fabs(tim - b.tim) < eps) return (x == b.x ? y < b.y : x < b.x);
return tim > b.tim;
}
};
int n;
priority_queue<Node> S;
//set<Node> S;
bool vis[MAXN];
int stc[MAXN], sc = 0;
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].v = read();
a[i].pre = i - 1, a[i].nxt = i + 1;
}
a[1].pre = 0, a[0].nxt = 1;
a[n].nxt = n + 1, a[n + 1].pre = n;
for(int i = 1; i < n; ++i) {
if(Check(i, i + 1)) {
S.push((Node){(long double)(a[i + 1].x - a[i].x) / (long double)(a[i].v - a[i + 1].v), i, i + 1});
}
}
while(!S.empty()) {
Node u = S.top(); S.pop();
if(u.x > u.y) swap(u.x, u.y);
if(vis[u.x] || vis[u.y]) continue;
vis[u.x] = vis[u.y] = true;
int A = a[u.x].pre, B = a[u.y].nxt;
if(A > B) swap(A, B);
a[A].nxt = B, a[B].pre = A;
if(A == 0 || B == n + 1) continue;
if(Check(A, B)) {
S.push((Node){(long double)(a[B].x - a[A].x) / (long double)(a[A].v - a[B].v), A, B});
}
}
for(int i = 1; i <= n; ++i) if(!vis[i]) stc[++sc] = i;
printf("%lld\n", sc);
for(int i = 1; i < sc; ++i) printf("%lld ", stc[i]);
if(sc) printf("%lld\n", stc[sc]);
return 0;
}
/*
3
10 15
30 5
50 -1
6
0 3
2 2
3 1
4 3
5 2
6 3
*/
详细
Test #1:
score: 100
Accepted
time: 0ms
memory: 5764kb
input:
1 -4 13
output:
1 1
result:
ok 2 lines
Test #2:
score: 0
Accepted
time: 3ms
memory: 5712kb
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: 5668kb
input:
3 -1000000000 1 999999999 0 1000000000 0
output:
3 1 2 3
result:
wrong answer 1st lines differ - expected: '1', found: '3'