| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 332510 | 2020-12-02T18:16:08 Z | pggp | 늑대인간 (IOI18_werewolf) | C++14 | 600 ms | 58872 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[22];
vector < int > back[22];
// forw – maksimum z przodu
// back – minimum z tyłu
bool db = false;
vector < int > s, e, l, r;
// przy bound nierówność ostra
int forw_max(int start, int bound){
int ans = 0;
int exp = 0;
int power = 1;
while(exp < 20 and forw[exp][start] >= bound){
exp++;
power *= 2;
}
if(exp > 19){
return power;
}
ans = power/2;
//if(db) cout << "ans = " << ans << endl;
while(power > 1){
exp--;
power /= 2;
if(forw[exp][start + ans] >= bound){
//if(db) cout << "power: " << power << "exp: " << exp << endl;
ans += power;
if(start + ans >= n){
return n;
}
}
}
return ans;
}
int back_min(int start, int bound){
int ans = 0;
int exp = 0;
int power = 1;
while(exp < 18 and back[exp][start] <= bound){
exp++;
power *= 2;
}
if(exp > 17){
return n - 1;
}
ans = power/2;
if(db) cout << "ans = " << ans << endl;
while(power > 1){
exp--;
power /= 2;
if(back[exp][start - ans] <= bound){
if(db) cout << "power: " << power << "exp: " << exp << endl;
ans += power;
if(start - ans <= 0){
return n;
}
}
}
return ans;
}
vector < bool > check(){
vector < bool > ans;
for (int i = 0; i < 20; ++i)
{
forw[i].clear();
forw[i].resize(n);
back[i].clear();
back[i].resize(n);
}
int power = 1;
for (int i = 0; i < 20; ++i)
{
for (int j = 0; j < n; ++j)
{
if(power == 1){
if(j == n){
forw[0][j] = A[n - 1];
}
else{
forw[i][j] = A[j + 1];
}
}
else{
if(j + power / 2 < n){
forw[i][j] = min(forw[i - 1][j], forw[i - 1][j + power / 2]);
}
else{
forw[i][j] = forw[i - 1][j];
}
}
}
power *= 2;
}
power = 1;
for (int i = 0; i < 20; ++i)
{
for(int j = 0; j < power and j < n and i > 0; j++){
back[i][j] = back[i - 1][j];
}
for (int j = power / 2; j < n; ++j)
{
if(power == 1){
if(j != 0){
back[i][j] = A[j - 1];
}
else{
back[i][j] = A[0];
}
}
else{
back[i][j] = max( back[i - 1][j], back[i - 1][j - power / 2]);
}
}
power *= 2;
}
if(db){
for (int i = 0; i < n; ++i)
{
cout << i << ": ";
for (int p = 0; p < 5; ++p)
{
cout << back[p][i] << " ";
}
cout << endl;
}
cout << endl;
}
for(int q = 0; q < quests; q++){
int pos_s = A_rev[s[q]];
int pos_e = A_rev[e[q]];
int a = forw_max(pos_s, l[q]);
int b = back_min(pos_e, r[q]);
if(db){
cout << "a = " << a << "; b = " << b << endl;
cout << "L = " << l[q] << "; r = " << r[q] << endl;
cout << "A[pos_s + a + 1]= " << A[pos_s + a + 1] << "; A[pos_e - b - 1] = " << A[pos_e - b - 1] << endl;
cout << "pos_s = " << pos_s << "; pos_e = " << pos_e << endl << endl;
cout << "A[pos_s] = " << A[pos_s] << "; A[pos_e] = " << A[pos_e] << endl << endl;
}
if(pos_s > pos_e){
ans.push_back(false);
}
else{
if(a + b >= pos_e - pos_s or pos_s == pos_e){
ans.push_back(true);
}
else{
ans.push_back(false);
}
}
}
return ans;
}
vector < int > check_validity(int N, vector < int > X, vector < int > Y, vector < int > S, vector < int > E, vector < int > L, vector < int > R){
vector < int > ans;
int Q = E.size();
quests = Q;
Ed.resize(N);
vector< int > emp;
s = S;
S=emp;
e = E;
E = emp;
l = L;
L = emp;
r = R;
R=emp;
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;
cur = Ed[cur][0];
cur_ind++;
}
else{
prev = cur;
A[cur_ind] = cur;
cur = Ed[cur][1];
cur_ind++;
}
}
A[N - 1] = cur;
}
}
for (int i = 0; i < N; ++i)
{
A_rev[A[i]] = i;
}
/*cout << "A: " << endl;
for (int i = 0; i < N; ++i)
{
cout << A[i] << " ";
}
cout << endl << "A_rev: " << endl;
for (int i = 0; i < N; ++i)
{
cout << A_rev[i] << " ";
}
cout << endl;*/
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
| # | 결과 | 실행 시간 | 메모리 | Grader output |
|---|---|---|---|---|
| 1 | Incorrect | 1 ms | 364 KB | Output isn't correct |
| 2 | Halted | 0 ms | 0 KB | - |
| # | 결과 | 실행 시간 | 메모리 | Grader output |
|---|---|---|---|---|
| 1 | Incorrect | 1 ms | 364 KB | Output isn't correct |
| 2 | Halted | 0 ms | 0 KB | - |
| # | 결과 | 실행 시간 | 메모리 | Grader output |
|---|---|---|---|---|
| 1 | Incorrect | 600 ms | 58872 KB | Output isn't correct |
| 2 | Halted | 0 ms | 0 KB | - |
| # | 결과 | 실행 시간 | 메모리 | Grader output |
|---|---|---|---|---|
| 1 | Incorrect | 1 ms | 364 KB | Output isn't correct |
| 2 | Halted | 0 ms | 0 KB | - |