QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#164168#7119. Longest Tripskip2004Compile Error//C++1411.4kb2023-09-04 20:28:352024-04-28 08:36:04

Judging History

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

  • [2024-04-28 08:36:04]
  • 管理员手动重测本题所有提交记录
查看
  • [2023-09-04 20:28:35]
  • 评测
查看
  • [2023-09-04 20:28:35]
  • 提交

answer

#include "longesttrip.h"

#include <cassert>
#include <cstdio>
#include <random>
#include <string>
#include <vector>
#include <algorithm>

static std::mt19937 gen(20040434);
int finde(int s, std::vector<int> a) {
	auto t = a;
	shuffle(t.begin(), t.end(), gen);
	for(;t.size() > 1;) {
		std::vector<int> A, B;
		for(int i = 0;i < (int) t.size();++i) {
			(i & 1 ? A : B).push_back(t[i]);
		}
		if(are_connected({s}, A)) {
			t = A;
		} else {
			t = B;
		}
	}
	return t[0];
}
std::pair<int, int> finde(std::vector<int> a, std::vector<int> b) {
	if(a.size() == 1 && b.size() == 1) {
		return {a[0], b[0]};
	}
	if(a.size() < b.size()) {
		auto [x, y] = finde(b, a);
		return {y, x};
	}
	std::vector<int> A, B;
	for(int i = 0;i < (int) a.size();++i) {
		(i & 1 ? A : B).push_back(a[i]);
	}
	if(are_connected(A, b)) {
		return finde(A, b);
	} else {
		return finde(B, b);
	}
}
std::vector<int> path(std::vector<int> now, std::vector<int> a) {
	std::vector<int> cl;
	for(;a.size();) {
		// if(cl.size() > now.size()) swap(now, cl);
		if(cl.size() == 1) a.push_back(cl[0]), cl = {};
		int fi = 1;
		shuffle(a.begin(), a.end(), gen);
		for(;a.size();) {
			int t = a.back(); a.pop_back();
			if(are_connected({now.back()}, {t})) {
				now.push_back(t);
				break;
			} else {
				if(fi) {
					if(cl.size()) {
						if(are_connected({now.back()}, cl)) {
							int z = finde(now.back(), cl);
							iter_swap(cl.begin(), find(cl.begin(), cl.end(), z));
							now.insert(now.end(), cl.begin(), cl.end());
							cl = {};
							a.push_back(t);
							break;
						}
					}
					fi = 0;
				}
				cl.push_back(t);
			}
		}
	}
	if(cl.size() && are_connected({now.back()}, cl)) {
		int t = finde(now.back(), cl);
		iter_swap(cl.begin(), find(cl.begin(), cl.end(), t));
		now.insert(now.end(), cl.begin(), cl.end());
		return now;
	}
	a = cl;
	if(a.empty()) return now;
	if(now.size() == 1) return a;
	if(are_connected({now[0]}, {now.back()})) {
		if(are_connected(now, a)) {
			auto [x, y] = finde(now, a);
			rotate(now.begin(), find(now.begin(), now.end(), x), now.end());
			iter_swap(a.end() - 1, find(a.begin(), a.end(), y));
			a.insert(a.end(), now.begin(), now.end());
			return a;
		} else {
			return now.size() < a.size() ? a : now;
		}
	} else {
		reverse(now.begin(), now.end());
		now.insert(now.end(), a.begin(), a.end());
		return now;
	}
}
std::vector<int> longest_trip(int N, int D) {
	std::vector<int> a(N);
	for(int i = 0;i < N;++i) {
		a[i] = i;
	}
	shuffle(a.begin(), a.end(), gen);
	std::vector<int> now = {a[0]};
	a.erase(a.begin());
	auto ans = path(now, a);
	if(ans.size() >= 280) exit(1);
	return path(now, a);
}

#ifdef zqj
static inline constexpr int maxNumberOfCalls = 32640;
static inline constexpr int maxTotalNumberOfCalls = 150000;
static inline constexpr int maxTotalNumberOfLandmarksInCalls = 1500000;
static int call_counter = 0;
static int total_call_counter = 0;
static int landmark_counter = 0;

static int C, N, D;
static std::vector<std::vector<int>> U;
static std::vector<bool> present;

static inline void protocol_violation(std::string message)
{
	printf("Protocol Violation: %s\n", message.c_str());
	exit(0);
}

bool are_connected(std::vector<int> A, std::vector<int> B)
{
	++call_counter;
	++total_call_counter;
	if (call_counter > maxNumberOfCalls || total_call_counter > maxTotalNumberOfCalls)
	{
		protocol_violation("too many calls");
	}

	int nA = A.size(), nB = B.size();
	landmark_counter += nA + nB;
	if (landmark_counter > maxTotalNumberOfLandmarksInCalls)
	{
		protocol_violation("too many elements");
	}

	if (nA == 0 || nB == 0)
	{
		protocol_violation("invalid array");
	}
	for (int i = 0; i < nA; ++i)
	{
		if (A[i] < 0 || N <= A[i])
		{
			protocol_violation("invalid array");
		}
		if (present[A[i]])
		{
			protocol_violation("invalid array");
		}
		present[A[i]] = true;
	}
	for (int i = 0; i < nA; ++i)
	{
		present[A[i]] = false;
	}
	for (int i = 0; i < nB; ++i)
	{
		if (B[i] < 0 || N <= B[i])
		{
			protocol_violation("invalid array");
		}
		if (present[B[i]])
		{
			protocol_violation("invalid array");
		}
		present[B[i]] = true;
	}
	for (int i = 0; i < nB; ++i)
	{
		present[B[i]] = false;
	}

	for (int i = 0; i < nA; ++i)
	{
		for (int j = 0; j < nB; ++j)
		{
			if (A[i] == B[j])
			{
				protocol_violation("non-disjoint arrays");
			}
		}
	}

	for (int i = 0; i < nA; ++i)
	{
		for (int j = 0; j < nB; ++j)
		{
			if (U[std::max(A[i], B[j])][std::min(A[i], B[j])] == 1)
			{
				return true;
			}
		}
	}

	return false;
}

int main()
{
	freopen("1.in", "r", stdin);
	assert(1 == scanf("%d", &C));
	int maximumCalls = 0;
	for (int c = 0; c < C; ++c)
	{
		call_counter = 0;
		assert(2 == scanf("%d %d", &N, &D));

		present.assign(N, false);
		U.resize(N);
		for (int i = 1; i < N; ++i)
		{
			U[i].resize(i);
			for (int j = 0; j < i; ++j)
			{
				assert(1 == scanf("%d", &U[i][j]));
			}
		}

		for (int i = 2; i < N; ++i)
		{
			for (int j = 1; j < i; ++j)
			{
				for (int k = 0; k < j; ++k)
				{
					if (U[i][j] + U[i][k] + U[j][k] < D)
					{
						printf("Insufficient Density\n");
						exit(0);
					}
				}
			}
		}

		std::vector<int> t = longest_trip(N, D);
		int l = t.size();
		for (int i = 1; i < l; ++i) {
			int a = t[i - 1];
			int b = t[i];
			if(U[std::max(a, b)][std::min(a, b)] == 0) {
				puts("error");
				exit(1);
			}
		}
		printf("%d\n", l);
		for (int i = 0; i < l; ++i)
		{
			printf(i == 0 ? "%d" : " %d", t[i]);
		}
		printf("\n");
		printf("%d\n", call_counter);

		maximumCalls = std::max(maximumCalls, call_counter);
		call_counter = 0;
	}
	printf("%d\n", maximumCalls);

	return 0;
}
#endif
#include "longesttrip.h"

#include <cassert>
#include <cstdio>
#include <random>
#include <string>
#include <vector>
#include <algorithm>

static std::mt19937 gen(20040434);
int finde(int s, std::vector<int> a) {
	auto t = a;
	shuffle(t.begin(), t.end(), gen);
	for(;t.size() > 1;) {
		std::vector<int> A, B;
		for(int i = 0;i < (int) t.size();++i) {
			(i & 1 ? A : B).push_back(t[i]);
		}
		if(are_connected({s}, A)) {
			t = A;
		} else {
			t = B;
		}
	}
	return t[0];
}
std::pair<int, int> finde(std::vector<int> a, std::vector<int> b) {
	if(a.size() == 1 && b.size() == 1) {
		return {a[0], b[0]};
	}
	if(a.size() < b.size()) {
		auto [x, y] = finde(b, a);
		return {y, x};
	}
	std::vector<int> A, B;
	for(int i = 0;i < (int) a.size();++i) {
		(i & 1 ? A : B).push_back(a[i]);
	}
	if(are_connected(A, b)) {
		return finde(A, b);
	} else {
		return finde(B, b);
	}
}
std::vector<int> path(std::vector<int> now, std::vector<int> a) {
	std::vector<int> cl;
	for(;a.size();) {
		// if(cl.size() > now.size()) swap(now, cl);
		if(cl.size() == 1) a.push_back(cl[0]), cl = {};
		int fi = 1;
		shuffle(a.begin(), a.end(), gen);
		for(;a.size();) {
			int t = a.back(); a.pop_back();
			if(are_connected({now.back()}, {t})) {
				now.push_back(t);
				break;
			} else {
				if(fi) {
					if(cl.size()) {
						if(are_connected({now.back()}, cl)) {
							int z = finde(now.back(), cl);
							iter_swap(cl.begin(), find(cl.begin(), cl.end(), z));
							now.insert(now.end(), cl.begin(), cl.end());
							cl = {};
							a.push_back(t);
							break;
						}
					}
					fi = 0;
				}
				cl.push_back(t);
			}
		}
	}
	if(cl.size() && are_connected({now.back()}, cl)) {
		int t = finde(now.back(), cl);
		iter_swap(cl.begin(), find(cl.begin(), cl.end(), t));
		now.insert(now.end(), cl.begin(), cl.end());
		return now;
	}
	a = cl;
	if(a.empty()) return now;
	if(now.size() == 1) return a;
	if(are_connected({now[0]}, {now.back()})) {
		if(are_connected(now, a)) {
			auto [x, y] = finde(now, a);
			rotate(now.begin(), find(now.begin(), now.end(), x), now.end());
			iter_swap(a.end() - 1, find(a.begin(), a.end(), y));
			a.insert(a.end(), now.begin(), now.end());
			return a;
		} else {
			return now.size() < a.size() ? a : now;
		}
	} else {
		reverse(now.begin(), now.end());
		now.insert(now.end(), a.begin(), a.end());
		return now;
	}
}
std::vector<int> longest_trip(int N, int D) {
	std::vector<int> a(N);
	for(int i = 0;i < N;++i) {
		a[i] = i;
	}
	shuffle(a.begin(), a.end(), gen);
	std::vector<int> now = {a[0]};
	a.erase(a.begin());
	return path(now, a);
}

#ifdef zqj
static inline constexpr int maxNumberOfCalls = 32640;
static inline constexpr int maxTotalNumberOfCalls = 150000;
static inline constexpr int maxTotalNumberOfLandmarksInCalls = 1500000;
static int call_counter = 0;
static int total_call_counter = 0;
static int landmark_counter = 0;

static int C, N, D;
static std::vector<std::vector<int>> U;
static std::vector<bool> present;

static inline void protocol_violation(std::string message)
{
	printf("Protocol Violation: %s\n", message.c_str());
	exit(0);
}

bool are_connected(std::vector<int> A, std::vector<int> B)
{
	++call_counter;
	++total_call_counter;
	if (call_counter > maxNumberOfCalls || total_call_counter > maxTotalNumberOfCalls)
	{
		protocol_violation("too many calls");
	}

	int nA = A.size(), nB = B.size();
	landmark_counter += nA + nB;
	if (landmark_counter > maxTotalNumberOfLandmarksInCalls)
	{
		protocol_violation("too many elements");
	}

	if (nA == 0 || nB == 0)
	{
		protocol_violation("invalid array");
	}
	for (int i = 0; i < nA; ++i)
	{
		if (A[i] < 0 || N <= A[i])
		{
			protocol_violation("invalid array");
		}
		if (present[A[i]])
		{
			protocol_violation("invalid array");
		}
		present[A[i]] = true;
	}
	for (int i = 0; i < nA; ++i)
	{
		present[A[i]] = false;
	}
	for (int i = 0; i < nB; ++i)
	{
		if (B[i] < 0 || N <= B[i])
		{
			protocol_violation("invalid array");
		}
		if (present[B[i]])
		{
			protocol_violation("invalid array");
		}
		present[B[i]] = true;
	}
	for (int i = 0; i < nB; ++i)
	{
		present[B[i]] = false;
	}

	for (int i = 0; i < nA; ++i)
	{
		for (int j = 0; j < nB; ++j)
		{
			if (A[i] == B[j])
			{
				protocol_violation("non-disjoint arrays");
			}
		}
	}

	for (int i = 0; i < nA; ++i)
	{
		for (int j = 0; j < nB; ++j)
		{
			if (U[std::max(A[i], B[j])][std::min(A[i], B[j])] == 1)
			{
				return true;
			}
		}
	}

	return false;
}

int main()
{
	freopen("1.in", "r", stdin);
	assert(1 == scanf("%d", &C));
	int maximumCalls = 0;
	for (int c = 0; c < C; ++c)
	{
		call_counter = 0;
		assert(2 == scanf("%d %d", &N, &D));

		present.assign(N, false);
		U.resize(N);
		for (int i = 1; i < N; ++i)
		{
			U[i].resize(i);
			for (int j = 0; j < i; ++j)
			{
				assert(1 == scanf("%d", &U[i][j]));
			}
		}

		for (int i = 2; i < N; ++i)
		{
			for (int j = 1; j < i; ++j)
			{
				for (int k = 0; k < j; ++k)
				{
					if (U[i][j] + U[i][k] + U[j][k] < D)
					{
						printf("Insufficient Density\n");
						exit(0);
					}
				}
			}
		}

		std::vector<int> t = longest_trip(N, D);
		int l = t.size();
		for (int i = 1; i < l; ++i) {
			int a = t[i - 1];
			int b = t[i];
			if(U[std::max(a, b)][std::min(a, b)] == 0) {
				puts("error");
				exit(1);
			}
		}
		printf("%d\n", l);
		for (int i = 0; i < l; ++i)
		{
			printf(i == 0 ? "%d" : " %d", t[i]);
		}
		printf("\n");
		printf("%d\n", call_counter);

		maximumCalls = std::max(maximumCalls, call_counter);
		call_counter = 0;
	}
	printf("%d\n", maximumCalls);

	return 0;
}
#endif
Source code, Language: C++14

Details 

answer.code: In function ‘std::pair<int, int> finde(std::vector<int>, std::vector<int>)’:
answer.code:32:22: warning: structured bindings only available with ‘-std=c++17’ or ‘-std=gnu++17’ [-Wc++17-extensions]
   32 |                 auto [x, y] = finde(b, a);
      |                      ^
answer.code: In function ‘std::vector<int> path(std::vector<int>, std::vector<int>)’:
answer.code:86:30: warning: structured bindings only available with ‘-std=c++17’ or ‘-std=gnu++17’ [-Wc++17-extensions]
   86 |                         auto [x, y] = finde(now, a);
      |                              ^
answer.code: At global scope:
answer.code:280:21: error: redefinition of ‘std::mt19937 gen’
  280 | static std::mt19937 gen(20040434);
      |                     ^~~
answer.code:10:21: note: ‘std::mt19937 gen’ previously declared here
   10 | static std::mt19937 gen(20040434);
      |                     ^~~
answer.code:281:5: error: redefinition of ‘int finde(int, std::vector<int>)’
  281 | int finde(int s, std::vector<int> a) {
      |     ^~~~~
answer.code:11:5: note: ‘int finde(int, std::vector<int>)’ previously defined here
   11 | int finde(int s, std::vector<int> a) {
      |     ^~~~~
answer.code:297:21: error: redefinition of ‘std::pair<int, int> finde(std::vector<int>, std::vector<int>)’
  297 | std::pair<int, int> finde(std::vector<int> a, std::vector<int> b) {
      |                     ^~~~~
answer.code:27:21: note: ‘std::pair<int, int> finde(std::vector<int>, std::vector<int>)’ previously defined here
   27 | std::pair<int, int> finde(std::vector<int> a, std::vector<int> b) {
      |                     ^~~~~
answer.code: In function ‘std::pair<int, int> finde(std::vector<int>, std::vector<int>)’:
answer.code:302:22: warning: structured bindings only available with ‘-std=c++17’ or ‘-std=gnu++17’ [-Wc++17-extensions]
  302 |                 auto [x, y] = finde(b, a);
      |                      ^
answer.code: At global scope:
answer.code:315:18: error: redefinition of ‘std::vector<int> path(std::vector<int>, std::vector<int>)’
  315 | std::vector<int> path(std::vector<int> now, std::vector<int> a) {
      |                  ^~~~
answer.code:45:18: note: ‘std::vector<int> path(std::vector<int>, std::vector<int>)’ previously defined here
   45 | std::vector<int> path(std::vector<int> now, std::vector<int> a) {
      |                  ^~~~
answer.code: In function ‘std::vector<int> path(std::vector<int>, std::vector<int>)’:
answer.code:356:30: warning: structured bindings only available with ‘-std=c++17’ or ‘-std=gnu++17’ [-Wc++17-extensions]
  356 |                         auto [x, y] = finde(now, a);
      |                              ^
answer.code: At global scope:
answer.code:370:18: error: redefinition of ‘std::vector<int> longest_trip(int, int)’
  370 | std::vector<int> longest_trip(int N, int D) {
      |                  ^~~~~~~~~~~~
answer.code:100:18: note: ‘std::vector<int> longest_trip(int, int)’ previously defined here
  100 | std::vector<int> longest_trip(int N, int D) {
      |                  ^~~~~~~~~~~~
English 繁體中文 简体中文

Server Time: 2024-12-04 04:08:44 | OpenSource Project