oj.uz

Submission #332437

# Submission time Handle Problem Language Result Execution time Memory
332437 2020-12-02T15:19:57 Z pggp Werewolf (IOI18_werewolf) C++14
0 / 100
 194 ms 35560 KB 
#include <bits/stdc++.h>

using namespace std;

vector < bool > used_wer;
vector < bool > used_hum;
vector < vector < int > > Ed;

int cur_R, cur_L;
int n, quests;

vector < int > A;
vector < int > A_rev;
vector < int > B;
vector < int > forw[20];
vector < int > back[20];
// forw – maksimum z przodu
// back – minimum z tyłu


vector < int > s, e, l, r;

// przy bound nierówność ostra
int forw_max(int start, int bound){
	int ans = 0;
	for (int i = start; i < n; ++i)
	{
		if(A[i] < bound)	return ans;
		ans++;
	}
	return ans;
}


int back_min(int start, int bound){
	int ans = 0;
	for (int i = start; i > 0; --i)
	{
		if(A[i] > bound)	return ans;
		ans++;
	}
	return ans;
}

vector < bool > check(){
	for (int i = 0; i < 20; ++i)
	{
		forw[i].clear();
		forw[i].resize(n);
		back[i].clear();
		back[i].resize(n);
	}
	vector < bool > ans;



	int power = 1;
	for (int i = 0; i < 20; ++i)
	{
		for (int j = 0; j + power - 1 < n; ++j)
		{
			if(power == 1){
				forw[i][j] = A[j];
			}
			else{
				forw[i][j] = max(forw[i - 1][j], forw[i - 1][j + power / 2]);
			}
		}
		power *= 2;
	}

	power = 1;
	for (int i = 0; i < 20; ++i)
	{
		for (int j = power - 1; j < n; ++j)
		{
			if(power == 0){
				back[i][j] = A[j];
			}
			else{
				back[i][j] = min( back[i - 1][j], forw[i - 1][j - power / 2]);
			}
		}
		power *= 2;
	}




	for(int q = 0; q < quests; q++){
		int pos_s = A_rev[s[q]];
		int pos_e = A_rev[e[q]];
		if(pos_s <= pos_e){
			ans.push_back(false);
		}
		else{
			int a = forw_max(pos_e, r[q]);
			int b = back_min(pos_s, l[q]);
			//cout << "a = " << a << "; b = " << b << endl;
			if(a + b >= pos_s - pos_e){
				ans.push_back(true);
			}
			else{
				ans.push_back(false);
			}
		}
		
	}
	

	return ans;
}

vector < bool > check_validity(int N, vector < int > X, vector < int > Y, vector < int > S, vector < int > E, vector < int > L, vector < int > R){
	vector < bool > ans;
	int Q = E.size();
	quests = Q;
	Ed.resize(N);
	s = S;
	e = E;
	l = L;
	r = R;
	n = N;
	used_wer.resize(N);
	used_hum.resize(N);
	for (int i = 0; i < X.size(); ++i)
	{
		Ed[X[i]].push_back(Y[i]);
		Ed[Y[i]].push_back(X[i]);
	}


	A.resize(N);
	A_rev.resize(N);
	B.resize(N);
	for (int i = 0; i < N; ++i)
	{
		if(Ed[i].size() == 1){
			A[0] = i;
			int prev = i;
			int cur = Ed[i][0];
			int cur_ind = 1;
			while(Ed[cur].size() > 1){
				if(Ed[cur][0] != prev){
					prev = cur;
					A[cur_ind] = cur;
					A_rev[cur] = cur_ind;
					cur = Ed[cur][0];
					cur_ind++;
				}
				else{
					prev = cur;
					A[cur_ind] = cur;
					cur = Ed[cur][1];
					cur_ind++;
				}
			}
			A[N - 1] = cur;
			A_rev[cur] = N - 1;
		}
	}

	for (int i = 0; i < N; ++i)
	{
		//cout << A[i] << " ";
	}


	

	vector < bool > a = check();
	B = A;
	for (int i = 0; i < A.size(); ++i)
	{
		A[i] = B[N - 1 - i];
		A_rev[A[i]] = i; 
	}
	vector < bool > b = check();

	for (int i = 0; i < a.size(); ++i)
	{
		ans.push_back(a[i] or b[i]);
	}
		
		//ans.push_back(to_return);
	return ans;
}

Compilation message

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

Subtask #1
0 / 7.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 492 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 492 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #3
0 / 34.0

# Verdict Execution time Memory Grader output
1 Runtime error 194 ms 35560 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #4
0 / 51.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 492 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -