Submission #764505

#	Time	Username	Problem	Language	Result	Execution time	Memory
764505		ono_de206	Werewolf (IOI18_werewolf)	C++14	34 / 100	1083 ms	62964 KiB

werewolf

#include "werewolf.h"
#include<bits/stdc++.h>
using namespace std;

#define in insert
#define all(x) x.begin(),x.end()
#define pb push_back
#define eb emplace_back
#define ff first
#define ss second

template<typename T>
void mxx(T &a, T b){if(b > a) a = b;}
template<typename T>
void mnn(T &a, T b){if(b < a) a = b;}

pair<int, int> operator+(pair<int, int> a, pair<int, int> b) {
	return make_pair(min(a.ff, b.ff), max(a.ss, b.ss));
}

vector<int> check_validity(int n, vector<int> X, vector<int> Y, vector<int> S, vector<int> E, vector<int> L, vector<int> R) {
	int Q = S.size();
	vector<int> ret(Q, 0), pos(n);
	vector<vector<int>> g(n);
	for(int i = 0; i < X.size(); i++) {
		g[X[i]].pb(Y[i]);
		g[Y[i]].pb(X[i]);
	}
	int st = 0;
	for(int i = 0; i < n; i++) {
		if(g[i].size() == 1) st = i;
	}
	vector<int> p;
	int x = st, y = g[st][0];
	p.pb(x);
	while(g[y].size() == 2) {
		p.pb(y);
		x ^= g[y][0] ^ g[y][1];
		swap(x, y);
	}
	p.pb(y);

	vector<int> LOG(n + 10, 0);
	for(int i = 2; i < n + 10; i++) {
		LOG[i] = LOG[i / 2] + 1;
	}

	vector<vector<pair<int, int>>> sp(n, vector<pair<int, int>>(20));
	for(int i = 0; i < n; i++) {
		sp[i][0] = {p[i], p[i]};
		pos[p[i]] = i;
	}

	for(int j = 1; j < 20; j++) {
		for(int i = 0; i < n; i++) {
			if(i + (1 << j) > n) break;
			sp[i][j] = sp[i][j - 1] + sp[i + (1 << (j - 1))][j - 1];
		}
	}

	auto get = [&](int l, int r) -> pair<int, int> {
		int id = LOG[r - l + 1];
		return sp[l][id] + sp[r - (1 << id) + 1][id];
	};

	for(int i = 0; i < Q; i++) {
		int s = S[i], e = E[i], l = L[i], r = R[i];
		int ans1 = 0, ans2 = 0;
		if(pos[s] < pos[e]) {
			int ll = 0, rr = (pos[e] - pos[s] + 1);
			while(rr - ll > 1) {
				int m = (rr + ll) / 2;
				int mn = get(pos[s], pos[s] + m).ff;
				if(mn < l) rr = m;
				else ll = m;
			}
			ans1 = pos[s] + ll;

			ll = 0, rr = (pos[e] - pos[s] + 1);
			while(rr - ll > 1) {
				int m = (rr + ll) / 2;
				int mx = get(pos[e] - m, pos[e]).ss;
				if(mx > r) rr = m;
				else ll = m;
			}
			ans2 = pos[e] - ll;
		} else {
			int ll = 0, rr = (pos[s] - pos[e] + 1);
			while(rr - ll > 1) {
				int m = (rr + ll) / 2;
				int mn = get(pos[s] - m, pos[s]).ff;
				if(mn < l) rr = m;
				else ll = m;
			}
			ans2 = pos[s] - ll;

			ll = 0, rr = (pos[s] - pos[e] + 1);
			while(rr - ll > 1) {
				int m = (rr + ll) / 2;
				int mx = get(pos[e], pos[e] + m).ss;
				if(mx > r) rr = m;
				else ll = m;
			}
			ans1 = pos[e] + ll;
		}
		ret[i] = (ans1 >= ans2);
	}

	return ret;
}

Compilation message (stderr)

werewolf.cpp: In function 'std::vector<int> check_validity(int, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
werewolf.cpp:25:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   25 |  for(int i = 0; i < X.size(); i++) {
      |                 ~~^~~~~~~~~~

• Subtask 1: 0 / 7
• Subtask 2: 0 / 8
• Subtask 3: 34 / 34
• Subtask 4: 0 / 51