QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#110488#2293. Boredom BusterzzzYhengCompile Error//C++149.2kb2023-06-02 16:42:402023-06-02 16:42:44

Judging History

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

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-06-02 16:42:44]
  • 评测
查看
  • [2023-06-02 16:42:40]
  • 提交

answer

#include "galacticparagons.h"
#include <bits/stdc++.h>

#define Fir first 
#define Sec second

using namespace std; 

const int MaxN = 100005; 

int n; 

struct node {
	int px, py; 
	int vx, vy; 
	
	node(int a = 0, int b = 0, int c = 0, int d = 0) {
		px = a, py = b, vx = c, vy = d; 
	}
}; 

void put(node x) {
	printf("node : px = %d, py = %d, vx = %d, vy = %d\n", x.px, x.py, x.vx, x.vy); 
}

vector<node> vec; 

deque<int> pos[MaxN];  

set<int> set1, set2; 

vector<node> iso; 

vector<int> ans;  

void revealCards(int x, int y) {
	printf("? %d %d\n", x, y); 
}
	
void solve1(node x, int px, int py) {
	// 一个孤点
//	puts("ans: "); 
//	for (int i = 1; i <= n; ++i) printf("%d ", ans[i]); 
//	puts(""); 
//	puts("solve1: "); 
//	put(x); 
//	printf("%d %d\n", px, py); 
	pair<int, int> p = revealCards(x.px, px); 
//	printf("p : %d %d\n", p.Fir, p.Sec); 
	if (p.Fir == p.Sec) {
		ans[x.px] = x.vx; 
		ans[x.py] = x.vy; 
	}
	else {
		ans[x.py] = x.vx; ans[px] = 0; 
		//exit(0); 
		solve1(node(x.px, px, x.vx, x.vy), x.py, py); 
	}
}

node solve2(node x, node y) {
	// 两个孤点
//	puts("ans: "); 
//	for (int i = 1; i <= n; ++i) printf("%d ", ans[i]); 
//	puts(""); 
//	puts("solve2: "); 
//	put(x), put(y); 
	pair<int, int> p = revealCards(x.px, y.px); 
//	printf("p : %d %d\n", p.Fir, p.Sec); 
	if (x.vx == p.Fir || x.vx == p.Sec) ans[x.py] = x.vy; 
	else ans[x.py] = x.vx; 
	if (y.vx == p.Fir || y.vx == p.Sec) ans[y.py] = y.vy; 
	else ans[y.py] = y.vx; 
	return node(x.px, y.px, p.Fir, p.Sec); 
}

void solve3(int id) {
	// 一个自环
	ans[vec[id].px] = ans[vec[id].py] = vec[id].vx; 
	set2.erase(vec[id].vx); 
	pos[vec[id].vx].clear(); 
}

void solve4(node x, node y) {
	// 两点孤链
//	puts("solve 4:"); 
//	put(x); 
//	put(y); 
	pair<int, int> p = revealCards(x.px, y.px); 
//	printf("p: %d %d\n", p.Fir, p.Sec); 
	if (p.Fir == p.Sec) {
		ans[x.px] = p.Fir, ans[y.px] = p.Sec; 
		ans[x.py] = x.vx, ans[y.py] = y.vy; 
	}
	else {
		if (x.vx == p.Fir || x.vx == p.Sec) ans[x.py] = x.vy; 
		else ans[x.py] = x.vx; 
		if (y.vy == p.Fir || y.vy == p.Sec) ans[y.py] = y.vx; 
		else ans[y.py] = y.vy; 
		iso.emplace_back(x.px, y.px, p.Fir, p.Sec); 
	}
	set2.erase(x.vy); 
	set1.erase(x.vx), set1.erase(y.vy); 
} 

void solve5(int id1, int id2) {
	// 链上两点
//	puts("solve 5:"); 
//	put(vec[id1]); 
//	put(vec[id2]); 
	pair<int, int> p = revealCards(vec[id1].px, vec[id2].px); 
	if (p.Fir == p.Sec) {
		ans[vec[id1].px] = ans[vec[id2].px] = p.Fir; 
		ans[vec[id1].py] = vec[id1].vx, ans[vec[id2].py] = vec[id2].vy; 
		set1.erase(vec[id1].vx), set2.erase(vec[id2].vy), set1.emplace(vec[id2].vy); 
		set2.erase(p.Fir); 
		pos[p.Fir].clear(); 
		pos[vec[id1].vx].clear(); 
		if (pos[vec[id2].vy].front() == id2) pos[vec[id2].vy].pop_front(); 
		else pos[vec[id2].vy].pop_back(); 
	}
	else {
		if (p.Fir == vec[id1].vy || p.Sec == vec[id1].vy) {
			if (p.Fir != vec[id1].vy) swap(p.Fir, p.Sec); 
			if (vec[id1].vx == p.Sec) {
				ans[vec[id1].py] = vec[id1].vy, ans[vec[id2].py] = vec[id2].vy; 
				iso.emplace_back(vec[id1].px, vec[id2].px, vec[id1].vx, vec[id2].vx);
				set1.erase(vec[id1].vx); 
				set2.erase(vec[id1].vy), set2.erase(vec[id2].vy), set1.emplace(vec[id2].vy); 
				pos[vec[id1].vx].clear(); 
				pos[vec[id1].vy].clear(); 
				if (pos[vec[id2].vy].front() == id2) pos[vec[id2].vy].pop_front(); 
				else pos[vec[id2].vy].pop_back(); 
			}
			else {
				ans[vec[id1].py] = vec[id1].vx, ans[vec[id2].py] = vec[id2].vx; 
				vec[id2].py = vec[id1].px; 
				set1.erase(vec[id1].vx); 
				set2.erase(vec[id1].vy), set1.emplace(vec[id1].vy); 
				pos[vec[id1].vx].clear(); 
				if (pos[vec[id1].vy].front() == id1) pos[vec[id1].vy].pop_front(); 
				else pos[vec[id1].vy].pop_back(); 
			}
		}
		else {
			ans[vec[id1].py] = ans[vec[id2].py] = vec[id1].vy; 
			vec[id2].py = vec[id1].px; 
			vec[id2].vx = vec[id1].vx; 
			set2.erase(vec[id1].vy); 
			pos[vec[id1].vy].clear(); 
			pos[vec[id1].vx].clear(); 
			pos[vec[id1].vx].emplace_back(id2); 
		}
	}
}

void solve6(node x, node y) {
	// 两点孤环
//	puts("solve 6:"); 
//	put(x); 
//	put(y); 
	pair<int, int> p = revealCards(x.px, y.px); 
	if (p.Fir == p.Sec) {
		if (x.vx == p.Fir) {
			ans[x.px] = ans[y.px] = x.vx; 
			ans[x.py] = ans[y.py] = x.vy; 
		}
		else {
			ans[x.px] = ans[y.px] = x.vy; 
			ans[x.py] = ans[y.py] = x.vx; 
		}
		set2.erase(x.vx), set2.erase(x.vy); 
	}
	else {
		solve6(node(x.px, y.px, p.Fir, p.Sec), node(x.py, y.py, p.Fir, p.Sec)); 
	}
}

void solve7(int id1, int id2) {
	// 环上两点
//	puts("solve 7:"); 
//	put(vec[id1]); 
//	put(vec[id2]); 
	swap(vec[id1].vx, vec[id1].vy); 
	pair<int, int> p = revealCards(vec[id1].px, vec[id2].px); 
	if (p.Fir == p.Sec) {
		ans[vec[id1].px] = ans[vec[id2].px] = vec[id1].vy; 
		ans[vec[id1].py] = vec[id1].vx, ans[vec[id2].py] = vec[id2].vy; 
		set2.erase(vec[id1].vx), set2.erase(vec[id2].vx), set2.erase(vec[id2].vy); 
		set1.emplace(vec[id1].vx), set1.emplace(vec[id2].vy); 
		pos[vec[id2].vx].clear(); 
		if (pos[vec[id1].vx].front() == id1) pos[vec[id1].vx].pop_front(); 
		else pos[vec[id1].vx].pop_back(); 
		if (pos[vec[id2].vy].front() == id2) pos[vec[id2].vy].pop_front(); 
		else pos[vec[id2].vy].pop_back(); 
	}	
	else {
		if (p.Fir == vec[id1].vy || p.Sec == vec[id1].vy) {
			if (p.Fir != vec[id1].vy) swap(p.Fir, p.Sec); 
			if (vec[id1].vx == p.Sec) {
				ans[vec[id1].py] = vec[id1].vy, ans[vec[id2].py] = vec[id2].vy;
				vec[id1].py = vec[id2].px; 
				set2.erase(vec[id2].vx), set1.emplace(vec[id2].vx); 
				set2.erase(vec[id2].vy), set1.emplace(vec[id2].vy); 
				if (pos[vec[id2].vx].front() == id2) pos[vec[id2].vx].pop_front(); 
				else pos[vec[id2].vx].pop_back(); 
				if (pos[vec[id2].vy].front() == id2) pos[vec[id2].vy].pop_front(); 
				else pos[vec[id2].vy].pop_back();  
			}
			else {
				ans[vec[id1].py] = vec[id1].vx, ans[vec[id2].py] = vec[id2].vx; 
				vec[id2].py = vec[id1].px; 
				set2.erase(vec[id1].vx), set1.emplace(vec[id1].vx); 
				set2.erase(vec[id1].vy), set1.emplace(vec[id1].vy); 
				if (pos[vec[id1].vx].front() == id1) pos[vec[id1].vx].pop_front(); 
				else pos[vec[id1].vx].pop_back(); 
				if (pos[vec[id1].vy].front() == id1) pos[vec[id1].vy].pop_front(); 
				else pos[vec[id1].vy].pop_back();  
			}
		}
		else {
			ans[vec[id1].py] = ans[vec[id2].py] = vec[id1].vy; 
			vec[id2].py = vec[id1].px; 
			vec[id2].vx = vec[id1].vx; 
			set2.erase(vec[id1].vy); 
			pos[vec[id1].vy].clear(); 
			if (pos[vec[id1].vx].front() == id1) pos[vec[id1].vx].pop_front(); 
			else pos[vec[id1].vx].pop_back(); 
			pos[vec[id1].vx].emplace_back(id2); 
		}
	}
}

void init() {
	ans.clear(); 
	vec.clear(); 
	set1.clear(), set2.clear(); 
	for (int i = 1; i <= n / 2; ++i) pos[i].clear(); 
	iso.clear(); 
}

int main() {
	cin >> n; 
	init(); 
	for (int i = 1; i <= n; i += 2) {
		pair<int, int> p = revealCards(i, i + 1); 
		vec.emplace_back(i, i + 1, p.Fir, p.Sec);
		pos[p.Fir].emplace_back(vec.size() - 1); 
		pos[p.Sec].emplace_back(vec.size() - 1);  
	}
	ans.resize(n + 1); 
	for (int i = 1; i <= n / 2; ++i) set2.emplace(i); 
//	for (int i = 0; i < vec.size(); ++i) {
//		printf("id = %d, ", i); 
//		put(vec[i]); 
//	}
//	puts(""); 
	while (set1.size() + set2.size()) {
		//printf("soso %d\n", pos[5][1]); 
//		puts("ans: "); 
//		for (int i = 1; i <= n; ++i) printf("%d ", ans[i]); 
//		puts(""); 
		if (set1.size()) {
			int x = *set1.begin(); 
			int id = pos[x][0]; 
			if (vec[id].vx != x) swap(vec[id].vx, vec[id].vy); 
			if (pos[vec[id].vy].size() == 1) {
//				puts("into iso"); 
//				put(vec[id]); 
				iso.emplace_back(vec[id]); 
				set1.erase(vec[id].vx), set1.erase(vec[id].vy); 
			}
			else {
				if (pos[vec[id].vy][0] != id) swap(pos[vec[id].vy][0], pos[vec[id].vy][1]); 
				int id2 = pos[vec[id].vy][1]; 
				if (vec[id2].vx != vec[id].vy) swap(vec[id2].vx, vec[id2].vy); 
				if (pos[vec[id2].vy].size() == 1) solve4(vec[id], vec[id2]); 
				else solve5(id, id2); 
			}
		}
		else {
			int x = *set2.begin(); 
//			printf("x = %d\n", x); 
			int id1 = pos[x][0], id2 = pos[x][1]; 
//			printf("id = %d, ", id1), put(vec[id1]); 
//			printf("id = %d, ", id2), put(vec[id2]); 
			if (id1 == id2) solve3(id1);
			else {
				if (vec[id1].vx != x) swap(vec[id1].vx, vec[id1].vy); 
				if (vec[id2].vx != x) swap(vec[id2].vx, vec[id2].vy); 
//				printf("id = %d, ", id1), put(vec[id1]); 
//			printf("id = %d, ", id2), put(vec[id2]); 
				if (vec[id1].vy == vec[id2].vy) solve6(vec[id1], vec[id2]); 
				else solve7(id1, id2); 
			}
		}
	}
//	puts("ans: "); 
//	for (int i = 1; i <= n; ++i) printf("%d ", ans[i]); 
//	puts(""); 
//	puts("into"); 
//	for (int i = 0; i < iso.size(); ++i) {
//		put(iso[i]); 
//	}
	
	while (iso.size()) {
		if (iso.size() >= 2) {
			node t1 = iso.back(); iso.pop_back(); 
			node t2 = iso.back(); iso.pop_back(); 
			iso.emplace_back(solve2(t1, t2)); 
		}
		else {
			node t = iso.back(); iso.pop_back(); 
			int pos1 = 0, pos2 = 0; 
			for (int i = 1; i <= n; ++i) {
				if (ans[i] == t.vx) pos1 = i; 
				if (ans[i] == t.vy) pos2 = i; 
			}
			solve1(t, pos1, pos2); 
		}
	}
	for (int i = 0; i < n; ++i) ans[i] = ans[i + 1]; 
	return ans; 
}
Source code, Language: C++14

Details 

answer.code:1:10: fatal error: galacticparagons.h: No such file or directory
    1 | #include "galacticparagons.h"
      |          ^~~~~~~~~~~~~~~~~~~~
compilation terminated.
English 繁體中文 简体中文

Server Time: 2024-11-29 20:32:16 | OpenSource Project