QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#258220#7015. Rikka with IlluminationssupepapupuWA 25ms3552kbC++172.7kb2023-11-19 16:07:362023-11-19 16:07:37

Judging History

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

  • [2023-11-19 16:07:37]
  • 评测
  • 测评结果:WA
  • 用时:25ms
  • 内存:3552kb
  • [2023-11-19 16:07:36]
  • 提交

answer

#include <bits/stdc++.h>

#define x first
#define y second
#define el '\n'
#define debug(x) cout << #x << ": " << x << el
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int N = 1010, INF = 0x3f3f3f3f, mod = 998244353;

pll operator-(pll a, pll b) {
    return {a.x - b.x, a.y - b.y};
}

ll operator^(pll a, pll b) {
    return a.x * b.y - a.y * b.x;
}

ll area(pll a, pll b, pll c) {
    return b - a ^ c - a;
}

int sign(ll a) {
    if (a > 0) return 1;
    if (a < 0) return -1;
    return 0;
}

pll q[N * 2];
pll lit[N];
vector<pii> rs[N * 2];

void solve() {
    int n, m; cin >> n >> m;
    for (int i = 0; i <= n * 2; ++i) rs[i].clear();
    for (int i = 0; i < n; ++i) {
        cin >> q[i].x >> q[i].y;
        q[i + n] = q[i];
    }
    q[n + n] = q[0], q[n + n + 1] = q[1];
    for (int i = 1; i <= m; ++i) {
        cin >> lit[i].x >> lit[i].y;
        int l = -1, r = -1;
        for (int j = 0, t = 0; j < n * 2; ++j) {
            if (sign(area(q[j], q[j + 1], q[j + 2])) == sign(area(q[j], q[j + 1], lit[i]))) {
                if (t == 2) {
                    r = j - 1;
                    break;
                }
                t = 1;
            } else {
                if (!t) continue;
                t = 2;
                if (l == -1) l = j;
            }
        }
        if (l != -1) rs[l].emplace_back(r, i), rs[l + n].emplace_back(r, i);
        // cout << l << ' ' << r << endl;
    }
    vector<int> way(n + 1);
    for (int i = 1; i <= n; ++i) {
        if (rs[i].empty()) continue;
        vector<int> V;
        int mr = -1;
        V.emplace_back(-1);
        for (auto[r, id]: rs[i]) {
            if (r > mr) {
                mr = r;
                V.back() = id;
            }
        }
        int last = i;
        while (mr < i + n - 1) {
            int nr = mr;
            V.emplace_back(-1);
            for (int j = last + 1; j <= mr + 1; ++j) {
                for (auto[r, id]: rs[j]) {
                    if (r > nr) {
                        nr = r;
                        V.back() = id;
                    }
                }
            }
            if (nr == mr) {
                break;
            }
            last = mr + 1;
            mr = nr;
        }
        if (V.back() != -1 && V.size() < way.size()) way.swap(V);
    }
    if (way.size() == n + 1) cout << -1 << el;
    else {
        cout << way.size() << el;
        for (int i: way) cout << i << ' ';
        cout << el;
    }
}

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    int tcase = 1;
    cin >> tcase;
    while (tcase--) solve();
}

详细

Test #1:

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

input:

1
3 3
0 0
1 0
0 1
-1 -1
3 -1
-1 3

output:

2
3 2 

result:

ok 1 cases.

Test #2:

score: -100
Wrong Answer
time: 25ms
memory: 3552kb

input:

100
13 17
-976 -766
-628 -956
462 -987
967 -997
981 -123
919 115
847 336
692 789
350 908
-558 996
-843 944
-944 400
-974 -476
-41876798 919231678
-375313647 26070145
-288061228 527643156
-93144407 730297
93699145 -260606010
-393321698 -339399089
644245933 784344503
-731740672 525632046
-32141854 114...

output:

2
12 4 
-1
-1
-1
-1
3
19 5 17 
-1
4
13 27 3 5 
-1
-1
-1
8
8 15 7 3 14 2 10 11 
4
6 8 5 7 
-1
3
3 2 7 
-1
-1
-1
-1
-1
4
2 5 13 8 
4
13 3 12 7 
4
7 1 2 5 
4
17 48 25 13 
4
52 19 2 13 
5
37 40 14 6 34 
37
90 58 8 35 22 18 33 44 71 83 26 76 38 51 7 20 84 4 9 12 14 32 45 24 78 68 73 67 23 29 11 48 49 85 ...

result:

wrong output format Expected EOLN