QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#60412#2174. Which Planet is This?!fstqwq#WA 236ms14824kbC++173.5kb2022-11-04 15:36:132022-11-04 15:36:16

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2022-11-04 15:36:16]
  • 评测
  • 测评结果:WA
  • 用时:236ms
  • 内存:14824kb
  • [2022-11-04 15:36:13]
  • 提交

answer

#include <bits/stdc++.h>

using namespace std;

constexpr int maxn = 1000005, base = 10000;

int fail[maxn];

void kmp(const vector<int> &s) {
	int n = (int)s.size() - 1;

	fail[0] = fail[1] = 0;
	for (int i = 1; i < n; i++) {
		int j = fail[i];
		while (j && s[i + 1] != s[j + 1])
			j = fail[j];
		
		if (s[i + 1] == s[j + 1])
			fail[i + 1] = j + 1;
		else
			fail[i + 1] = 0;
	}
}

vector<int> match(const vector<int> &s, const vector<int> &t) {
	int j = 0; // s in t, both 1-based

	vector<int> ans;
	for (int i = 1; i < (int)t.size(); i++) {
		while (j && s[j + 1] != t[i])
			j = fail[j];
		
		if (s[j + 1] == t[i])
			j++;
		
		if (j == (int)s.size() - 1)
			ans.push_back(i);
	}

	return ans;
}

vector<int> solve(int l, int r, const vector<vector<int>> &vec) {
	if (l == r)
		return vec[l];
	
	int mid = (l + r) / 2;
	auto u = solve(l, mid, vec), v = solve(mid + 1, r, vec);
	
	sort(u.begin(), u.end());
	sort(v.begin(), v.end());

	vector<int> c;
	int pt = 0;
	for (int x : u) {
		while (pt < (int)v.size() && v[pt] < x)
			pt++;
		
		if (pt < (int)v.size() && v[pt] == x)
			c.push_back(x);
	}

	return c;
}

int main() {

	int n;
	scanf("%d", &n);

	// vector<int> ax, ay, bx, by;
	// ax.resize(n + 1);
	// ay.resize(n + 1);
	// bx.resize(n * 2 + 1);
	// by.resize(n * 2 + 1);

	map<int, vector<int> > mpa, mpb, oa, ob;

	for (int i = 1; i <= n * 2; i++) {
		int xa, xb, ya, yb;
		scanf("%d.%d %d.%d", &xa, &xb, &ya, &yb);

		int u = xa * base + xb, v = ya * base + yb;
		v += 180 * base;

		// y += 180;

		// int u = (int)(x * base + 0.5), v = (int)(y * base + 0.5);

		(i <= n ? mpa[u] : mpb[u]).push_back(v);
	}
	
	// oa = mpa;
	// ob = mpb;

	bool bad = false;

	for (auto &[u, vec] : mpa) {
		if (!mpb.count(u) || mpb[u].size() != vec.size()) {
			bad = true;
			break;
		}

		sort(vec.begin(), vec.end());
		sort(mpb[u].begin(), mpb[u].end());

		oa[u] = vec;
		ob[u] = mpb[u];
		
		auto work = [] (vector<int> &vec) {
			// printf("(");
			// for (int x : vec)
			// 	printf(" %d", x);
			// printf(" ) -> (");

			vec.insert(vec.begin(), vec.back());
			for (int i = (int)vec.size() - 1; i > 0; i--)
				vec[i] -= vec[i - 1];
			
			for (int &x : vec)
				if (x < 0)
					x += 360 * base;
			
			vec[0] = 0;

			// for (int x : vec)
			// 	printf(" %d", x);
			// printf(")\n");
		};

		mpb[u].insert(mpb[u].end(), mpb[u].begin(), mpb[u].end());

		work(vec);
		work(mpb[u]);
	}

	if (bad) {
		printf("Different\n");
		return 0;
	}

	vector<vector<int>> res;

	for (auto &[u, vec] : mpa) {
		// printf("u = %d\n", u);
		// printf("vec:");
		// for (int x : vec)
		// 	printf(" %d", x);
		// printf("\n");
		// printf("mpb:");
		// for (int x : mpb[u])
		// 	printf(" %d", x);
		// printf("\n");

		kmp(vec);

		auto tv = match(vec, mpb[u]);

		// printf("tv:");
		// for (int x : tv)
		// 	printf(" %d", x);
		// printf("\n");

		res.push_back(vector<int>());

		int len = (int)oa[u].size();

		for (int i : tv)
			if (i - len < len) {
				int tmp = ob[u][i - len] - oa[u][0];

				if (tmp < 0)
					tmp += 360 * base;

				res.back().push_back(tmp);
			}
		
		// printf("? ");
		// for (int x : res.back())
		// 	printf("%d ", x);
		// printf("\n\n");

		memset(fail, 0, sizeof(int) * ((int)vec.size() + 3));
	}

	vector<int> ans = solve(0, (int)res.size() - 1, res);

	if (!ans.empty())
		printf("Same\n");
	else
		printf("Different\n");

	return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 3484kb

input:

3
10 0
20 40
30 -15
40 -15
20 0
30 40

output:

Different

result:

ok single line: 'Different'

Test #2:

score: -100
Wrong Answer
time: 236ms
memory: 14824kb

input:

359998
-0.0045 96.8638
-0.0045 -79.2284
-0.0045 -50.4113
-0.0045 -79.0394
-0.0045 -24.9710
-0.0045 -142.9880
-0.0045 50.6344
-0.0045 125.9464
-0.0045 -17.3039
-0.0045 42.3454
-0.0045 130.6138
-0.0045 -106.4363
-0.0045 -95.9378
-0.0045 90.7312
-0.0045 75.7615
-0.0045 -66.9785
-0.0045 -81.0752
-0.0045...

output:

Different

result:

wrong answer 1st lines differ - expected: 'Same', found: 'Different'