QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#155571#7015. Rikka with IlluminationsPetroTarnavskyi#RE 1ms3444kbC++173.0kb2023-09-01 20:33:102023-09-01 20:33:11

Judging History

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

  • [2023-09-01 20:33:11]
  • 评测
  • 测评结果:RE
  • 用时:1ms
  • 内存:3444kb
  • [2023-09-01 20:33:10]
  • 提交

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 = 1;
			do {
				v = f[v];
				cnt++;
			} while (v != -1 && !contains(v, l[i]));
			if (v != -1 && 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: 3444kb

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
Runtime Error

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:


result: