oj.uz

Submission #764505

# Submission time Handle Problem Language Result Execution time Memory
764505 2023-06-23T13:36:36 Z ono_de206 Werewolf (IOI18_werewolf) C++14
34 / 100
 1083 ms 62964 KB 
#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

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.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 468 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 468 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #3
34.0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 986 ms 62964 KB Output is correct
2 Correct 866 ms 62960 KB Output is correct
3 Correct 924 ms 62960 KB Output is correct
4 Correct 1022 ms 62964 KB Output is correct
5 Correct 924 ms 62852 KB Output is correct
6 Correct 1083 ms 62856 KB Output is correct
7 Correct 826 ms 62960 KB Output is correct
8 Correct 819 ms 62960 KB Output is correct
9 Correct 277 ms 62960 KB Output is correct
10 Correct 259 ms 62840 KB Output is correct
11 Correct 285 ms 62860 KB Output is correct
12 Correct 299 ms 62856 KB Output is correct
13 Correct 988 ms 62956 KB Output is correct
14 Correct 785 ms 62856 KB Output is correct
15 Correct 805 ms 62952 KB Output is correct
16 Correct 808 ms 62952 KB Output is correct
17 Correct 803 ms 62960 KB Output is correct

Subtask #4
0 / 51.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 468 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -