QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#22645#2365. Flight CollisionSuzt_ilymtics#WA 3ms3720kbC++142.2kb2022-03-10 14:40:412022-04-30 01:29:13

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:29:13]
  • 评测
  • 测评结果:WA
  • 用时:3ms
  • 内存:3720kb
  • [2022-03-10 14:40:41]
  • 提交

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'