QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#22789#2365. Flight CollisionSuzt_ilymtics#WA 3ms5776kbC++142.2kb2022-03-10 16:36:352022-04-30 01:40:34

Judging History

你现在查看的是最新测评结果

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2022-04-30 01:40:34]
  • 评测
  • 测评结果:WA
  • 用时:3ms
  • 内存:5776kb
  • [2022-03-10 16:36:35]
  • 提交

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){1.0 * (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 20
50 30

6
0 3
2 2
3 1
4 3
5 2
6 3
*/

詳細信息

Test #1:

score: 100
Accepted
time: 1ms
memory: 5736kb

input:

1
-4 13

output:

1
1

result:

ok 2 lines

Test #2:

score: 0
Accepted
time: 1ms
memory: 5776kb

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: 5764kb

input:

3
-1000000000 1
999999999 0
1000000000 0

output:

3
1 2 3

result:

wrong answer 1st lines differ - expected: '1', found: '3'