QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#657137 | #7015. Rikka with Illuminations | Ashbourne | WA | 77ms | 34708kb | C++20 | 2.0kb | 2024-10-19 14:15:02 | 2024-10-19 14:15:02 |
Judging History
answer
#include<bits/stdc++.h>
#define int long long
#define pii pair<int, int>
using namespace std;
const int N = 1005;
int vis[N][2 * N];
int len[N][2 * N];
int n, m;
int add(int x, int k){
return 1 + (x - 1 + k) % n;
}
int dis(int x0, int x1, int y0, int y1, int x, int y){
return (y1 - y0) * (x - x0) - (x1 - x0) * (y - y0);
}
void solve(){
cin >> n >> m;
// clear()
for(int i = 1;i <= m; ++ i)
for(int j = 1; j <= 2 * n + 1; ++ j) vis[i][j] = len[i][j] = 0;
//
vector<pii> a(n + 1);
for(int i = 1; i <= n; ++ i){
int x, y; cin >> x >> y;
a[i] = {x, y};
}
for(int i = 1; i <= m; ++ i){
int x, y; cin >> x >> y;
for(int j = 1; j <= n; ++ j){
auto [a1, a2] = a[j];
auto [b1, b2] = a[add(j, 1)];
auto [c1, c2] = a[add(j, 2)];
int d1 = dis(a1, b1, a2, b2, x, y) > 0 ? 1 : -1, d2 = dis(a1, b1, a2, b2, c1, c2) > 0 ? 1 : -1;
if(d1 * d2 < 0) vis[i][j] = vis[i][j + n] = 1;
}
}
for(int i = 1; i <= m; ++ i){
for(int j = 2 * n; j >= 1; -- j){
if(vis[i][j]) len[i][j] = len[i][j + 1] + 1;
else len[i][j] = 0;
}
}
vector<int> f(2 * n, 0), ker(2 * n, -1);
for(int j = 1; j <= 2 * n; ++ j){
for(int i = 1; i <= m; ++ i){
if(f[j] < len[i][j]){
f[j] = len[i][j];
ker[j] = i;
}
}
}
int ans = 1e14;
vector<int> nans;
for(int i = 1; i <= n; ++ i){
vector<int>rans;
int l = i, r = i + f[i], cs = 1;
rans.push_back(ker[i]);
while(l < r && r < i + n){
int nr = r, tt;
for(int j = l + 1; j <= r; ++ j){
if(nr < j + f[j]){
nr = j + f[j];
tt = ker[j];
// cout << tt << endl;
}
}
l = r;
r = nr;
rans.push_back(tt);
++cs;
}
if(r >= i + n) {
if(ans > cs){
ans = cs;
nans = rans;
}
}
}
// cout << (ans == 1e14? -1: ans) << endl;
if(ans == 1e14) cout << -1 << endl;
else{
cout << ans << endl;
for(auto x: nans) cout << x << " ";
cout << endl;
}
}
signed main(){
ios::sync_with_stdio(0);
int T;
cin >> T;
while(T--) solve();
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 1ms
memory: 5624kb
input:
1 3 3 0 0 1 0 0 1 -1 -1 3 -1 -1 3
output:
2 2 1
result:
ok 1 cases.
Test #2:
score: -100
Wrong Answer
time: 77ms
memory: 34708kb
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 5 1 -1 -1 -1 -1 3 17 19 5 -1 4 13 27 3 5 -1 -1 -1 8 8 15 7 3 14 2 10 11 4 7 6 8 5 -1 3 3 2 7 -1 -1 -1 -1 -1 4 8 2 5 13 4 13 3 12 7 4 5 7 1 2 4 17 48 25 13 4 13 22 38 2 5 37 40 14 6 34 37 88 31 5 40 28 1 59 42 21 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