QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#155579 | #7015. Rikka with Illuminations | PetroTarnavskyi | TL | 1ms | 3800kb | C++17 | 3.1kb | 2023-09-01 20:41:49 | 2023-09-01 20:41:50 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define FOR(i, a, b) for (int i = (a); i < (b); i++)
#define RFOR(i, a, b) for (int i = (a) - 1; i >= (b); i--)
#define FILL(a, b) memset(a, b, sizeof(a))
#define SZ(a) int(a.size())
#define ALL(a) a.begin(), a.end()
#define PB push_back
#define MP make_pair
#define F first
#define S second
typedef long long LL;
typedef vector<int> VI;
typedef pair<int, int> PII;
typedef double db;
const int MAX = 1 << 10;
struct Point
{
int x, y;
Point() {}
Point(int _x, int _y): x(_x), y(_y) {}
Point operator-(const Point& p) const
{
return {x - p.x, y - p.y};
}
LL operator*(const Point& p) const
{
return (LL)x * p.y - (LL)p.x * y;
}
};
int n, m;
int l[MAX], r[MAX];
int f[MAX];
pair<int, int> vec[47];
bool used[MAX];
int h(int i, int j)
{
int sz = 0;
vec[sz++] = {l[i], -1};
vec[sz++] = {r[i], 1};
if (l[i] > r[i])
{
vec[sz++] = {n, 1};
vec[sz++] = {0, -1};
}
vec[sz++] = {l[j], 1};
vec[sz++] = {r[j], -1};
if (l[j] > r[j])
{
vec[sz++] = {n, -1};
vec[sz++] = {0, 1};
}
vec[sz++] = {n, 0};
sort(vec, vec + sz);
int bal = 0;
int s = 0;
FOR(k, 0, sz)
{
if (bal == 1)
{
s += vec[k].first - vec[k - 1].first;
}
bal += vec[k].second;
}
return s;
}
int contains(int i, int x)
{
if (l[i] < r[i])
return l[i] <= x && x <= r[i];
return l[i] <= x || x <= r[i];
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
int t;
cin >> t;
while (t--)
{
cin >> n >> m;
vector<Point> p(n);
for (Point& pi : p)
cin >> pi.x >> pi.y;
p.push_back(p[0]);
p.push_back(p[1]);
FILL(l, -1);
FILL(r, -1);
FILL(f, -1);
FOR(i, 0, m)
{
Point q;
cin >> q.x >> q.y;
FOR(j, 0, n)
{
LL prod1 = (p[j + 1] - p[j]) * (q - p[j]);
LL prod2 = (p[j + 2] - p[j + 1]) * (q - p[j + 1]);
if (prod1 > 0 && prod2 < 0)
{
assert(l[i] == -1);
l[i] = (j + 1) % n;
}
if (prod1 < 0 && prod2 > 0)
{
assert(r[i] == -1);
r[i] = (j + 1) % n;
}
}
assert(l[i] != -1 && r[i] != -1 && l[i] != r[i]);
}
FOR(j, 0, m)
cin >> l[j] >> r[j];
FOR(i, 0, m)
{
int mx = 0;
FOR(j, 0, m)
{
if (l[i] != l[j] && contains(i, l[j]))
{
int cur = h(i, j);
if (cur > mx)
{
mx = cur;
f[i] = j;
}
}
}
}
int mn = m + 1, bestV = -1;
FOR(i, 0, m)
{
int v = i;
int cnt = 0;
FOR(j, 0, m)
used[j] = 0;
used[v] = 1;
do {
used[v] = 1;
v = f[v];
cnt++;
} while (v != -1 && used[v] == 0);//!contains(v, l[i]));
if (v == i && cnt < mn)
{
mn = cnt;
bestV = i;
}
}
if (bestV == -1)
{
cout << "-1\n";
}
else
{
cout << mn << "\n";
int v = bestV;
FILL(used, 0);
FOR(i, 0, mn)
{
if (i != 0)
cout << " ";
cout << v + 1;
for (int j = l[v]; j != r[v]; j = (j + 1) % n)
used[j] = true;
v = f[v];
}
FOR(j, 0, n)
assert(used[j]);
cout << "\n";
}
}
}
详细
Test #1:
score: 100
Accepted
time: 1ms
memory: 3800kb
input:
1 3 3 0 0 1 0 0 1 -1 -1 3 -1 -1 3
output:
2 1 2
result:
ok 1 cases.
Test #2:
score: -100
Time Limit Exceeded
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...