Submission #950910

# Submission time Handle Problem Language Result Execution time Memory
950910 2024-03-21T01:55:03 Z phoenix0423 Library (JOI18_library) C++17
Compilation error
0 ms 0 KB
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pll;
#define fastio ios::sync_with_stdio(false), cin.tie(0)
#define pb push_back
#define eb emplace_back
#define f first
#define s second
#define int long long
#define lowbit(x) x&-x
const int maxn = 1005;
#include "library.h"
int n;
deque<int> dq;
set<int> st;
int deg[maxn];
vector<int> adj[maxn];
int ed[maxn];
int eg = 0;

int qry(vector<int> a){
	int op = Query(a);
	return op < a.size();
}
void add(int a, int b){
	adj[a].pb(b);
	adj[b].pb(a);
	deg[a] ++, deg[b] ++;
	if(deg[a] == 2) st.insert(a);
	if(deg[b] == 2) st.insert(b);
	if(deg[a] == 1 && deg[b] == 1) ed[a] = 1;
	eg++;
}

void fix(){
	for(int i = 1; i <= n; i++){
		if(!ed[i] && deg[i] == 1) deg[i] = 2;
		if(ed[i]) ed[i] = 0;
	}
}
void Solve(int _n){
	n = _n;
	vector<int> q;
	while(eg < n - 1){
		vector<int> cand;
		for(int j = 1; j <= n; j++) if(!st.count(j) && !ed[j]) cand.pb(j);
		if(cand.size() < 2){
			fix();
			continue;
		}
		int l = 0, r = cand.size() - 1;
		int ok = 0;
		while(l < r){
			int m = (l + r) / 2;
			vector<int> a, b;
			for(int i = 0; i <= m; i++) a.pb(cand[i]);
			for(int i = m + 1; i <= r; i++) b.pb(cand[i]);
			if(qry(a)) r = m, ok = 1;
			else if(qry(b)) l = m + 1, ok = 1;
			else break;
		}
		if(r == l + 1 && ok){
			add(cand[l], cand[r]);
			continue;
		}
		int m = (l + r) / 2;
		int L = l, R = m;
		while(L < R){
			int mid = (L + R) / 2;
			vector<int> a;
			for(int i = m + 1; i < r; i++) a.pb(cand[i]);
			for(int i = L; i <= mid; i++) a.pb(cand[i]);
			if(qry(a)) R = m;
			else L = m + 1;
		}
		int fr = cand[L];
		L = m + 1, R = r;
		while(L < R){
			int mid = (L + R) / 2;
			vector<int> a;
			a.pb(fr);
			for(int i = L; i <= mid; i++) a.pb(cand[i]);
			if(qry(a)) R = m;
			else L = m + 1;
		}
		if(!ok){
			vector<int> a = {fr, cand[L]};
			if(!qry(a)){
				fix();
				continue;
			}
		}
		add(fr, cand[L]);
	}
	int pos;
	for(int i = 1; i <= n; i++){
		if(deg[i] == 1){
			pos = i;
			break;
		}
	}
	vector<int> ans;
	int prev = -1;
	while(true){
		ans.pb(pos);
		int ok = 0;
		for(auto x : adj[pos]){
			if(x != prev){
				prev = pos, pos = x, ok = 1;
				break;
			}
		}
		if(!ok) break;
	}
	Answer(ans);
}
// signed main(void){
// 	int n;
// 	cin>>n;
// 	Solve(n);
// }

Compilation message

library.cpp: In function 'long long int qry(std::vector<long long int>)':
library.cpp:24:12: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   24 |  return op < a.size();
      |         ~~~^~~~~~~~~~
/usr/bin/ld: /tmp/ccBR5p2W.o: in function `main':
grader.cpp:(.text.startup+0x25): undefined reference to `Solve(int)'
/usr/bin/ld: /tmp/ccqxjA8T.o: in function `qry(std::vector<long long, std::allocator<long long> >)':
library.cpp:(.text+0x59): undefined reference to `Query(std::vector<long long, std::allocator<long long> > const&)'
/usr/bin/ld: /tmp/ccqxjA8T.o: in function `Solve(long long)':
library.cpp:(.text+0x565): undefined reference to `Query(std::vector<long long, std::allocator<long long> > const&)'
/usr/bin/ld: library.cpp:(.text+0x65d): undefined reference to `Query(std::vector<long long, std::allocator<long long> > const&)'
/usr/bin/ld: library.cpp:(.text+0xaa9): undefined reference to `Query(std::vector<long long, std::allocator<long long> > const&)'
/usr/bin/ld: library.cpp:(.text+0xcaa): undefined reference to `Query(std::vector<long long, std::allocator<long long> > const&)'
/usr/bin/ld: /tmp/ccqxjA8T.o:library.cpp:(.text+0xe0b): more undefined references to `Query(std::vector<long long, std::allocator<long long> > const&)' follow
/usr/bin/ld: /tmp/ccqxjA8T.o: in function `Solve(long long)':
library.cpp:(.text+0xf3d): undefined reference to `Answer(std::vector<long long, std::allocator<long long> > const&)'
collect2: error: ld returned 1 exit status