QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#155589#7015. Rikka with IlluminationsPetroTarnavskyiCompile Error//C++173.3kb2023-09-01 20:53:472023-09-01 20:53:48

Judging History

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

  • [2023-09-01 20:53:48]
  • 评测
  • [2023-09-01 20:53:47]
  • 提交

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];
}

bool check(VI ans)
{
	FILL(used, 0);
	for(int v : ans)
	{
		for (int j = l[v]; j != r[v]; j = (j + 1) % n)
			used[j] = true;
	}	
	FOR(j, 0, n)
		if(!used[j])
			return 0;
	return 1;
}

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;
					}
				}
			}
			assert(f[i] != i);
		}
		int mn = m + 1, bestV = -1;
		FOR(i, 0, m)
		{
			int v = i;
			int cnt = 0;
			FILL(used, 0);
			while(true)
			{
				if(v == -1 || used[v])
					break;
				used[v] = 1;
				v = f[v];
				cnt++;
			}
			
			if (v == i && cnt < mn)
			{
				mn = cnt;
				bestV = i;
			}
		}
		if (bestV == -1)
		{
			VI all(m);
			iota(ALL(all), 0);
			assert(check(all) == 0);

			cout << "-1\n";
		}
		else
		{
			VI ans = {bestV};
			FOR(i, 0, mn - 1)
				ans.PB(f[ans.back()]);
			
			assert(check(ans));
			
			cout << SZ(ans) << "\n";
			FOR(i, 0, SZ(ans))
			{
				if(i != 0)
					cout << " ";
				cout << ans[i] + 1;
			
			cout << "\n";
		}
	}
}

详细

answer.code: In function ‘int main()’:
answer.code:201:2: error: expected ‘}’ at end of input
  201 | }
      |  ^
answer.code:97:1: note: to match this ‘{’
   97 | {
      | ^