| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 81516 |
2018-10-25T07:55:41 Z |
zubec |
Werewolf (IOI18_werewolf) |
C++14 |
|
592 ms |
27572 KB |
#include "werewolf.h"
#include <bits/stdc++.h>
using namespace std;
const int N = 200100;
vector <int> g[N];
int a[N], pos[N], t[2][N*4];
void update(int v, int l, int r, int pos, int x){
if (l == r){
t[0][v] = x;
t[1][v] = x;
return;
}
int mid = (l+r)>>1;
if (pos <= mid)
update(v+v, l, mid, pos, x); else
update(v+v+1, mid+1, r, pos, x);
t[0][v] = min(t[0][v+v], t[0][v+v+1]);
t[1][v] = max(t[1][v+v], t[1][v+v+1]);
}
int getRMn(int v, int l, int r, int pos, int x){
if (l == r){
return l;
}
int mid = (l+r)>>1;
if (mid <= pos){
return getRMn(v+v+1, mid+1, r, pos, x);
}
if (t[0][v+v] < x){
return getRMn(v+v, l, mid, pos, x);
}
return getRMn(v+v+1, mid+1, r, pos, x);
}
int getLMn(int v, int l, int r, int pos, int x){
if (l == r){
return l;
}
int mid = (l+r)>>1;
if (pos <= mid+1)
return getLMn(v+v, l, mid, pos, x);
if (t[0][v+v+1] < x)
return getLMn(v+v+1, mid+1, r, pos, x);
return getLMn(v+v, l, mid, pos, x);
}
int getRMx(int v, int l, int r, int pos, int x){
if (l == r){
return l;
}
int mid = (l+r)>>1;
if (mid <= pos){
return getRMx(v+v+1, mid+1, r, pos, x);
}
if (t[1][v+v] > x){
return getRMx(v+v, l, mid, pos, x);
}
return getRMx(v+v+1, mid+1, r, pos, x);
}
int getLMx(int v, int l, int r, int pos, int x){
if (l == r){
return l;
}
int mid = (l+r)>>1;
if (pos <= mid+1)
return getLMx(v+v, l, mid, pos, x);
if (t[1][v+v+1] > x)
return getLMx(v+v+1, mid+1, r, pos, x);
return getLMx(v+v, l, mid, pos, x);
}
std::vector<int> check_validity(int N, std::vector<int> X, std::vector<int> Y, std::vector<int> S, std::vector<int> E, std::vector<int> L, std::vector<int> R) {
for (int i = 0; i < N; i++){
g[i].clear();
}
for (int i = 0; i < X.size(); i++){
g[X[i]].push_back(Y[i]);
g[Y[i]].push_back(X[i]);
}
int cur = 0;
for (int i = 0; i < N; i++){
if (g[i].size() == 1){
cur = i;
break;
}
}
int prev = -1;
for (int i = 0; i < N; i++){
pos[cur] = i;
a[i] = cur;
update(1, 0, N-1, i, cur);
for (int j = 0; j < g[cur].size(); j++){
int to = g[cur][j];
if (to == prev)
continue;
prev = cur;
cur = to;
break;
}
}
vector <int> A;
for (int ii = 0; ii < S.size(); ii++){
int s = S[ii], e = E[ii];
int l = L[ii], r = R[ii];
int x1 = getLMn(1, 0, N-1, pos[s], l);
int y1 = getRMn(1, 0, N-1, pos[s], l);
int x2 = getLMx(1, 0, N-1, pos[e], r);
int y2 = getRMx(1, 0, N-1, pos[e], r);
if (a[x1] < l)
++x1;
if (a[y1] < l)
--y1;
if (a[x2] > r)
++x2;
if (a[y2] > r)
--y2;
int bb = 0;
//cout << "kek " << x1 << ' ' << y1 << " " << x2 << ' ' << y2 << endl;
int x3 = max(x1, x2);
int y3 = min(y1, y2);
if (x3 <= y3)
bb = 1;
A.push_back(bb);
}
return A;
}
/**
5 4 1
1 0
0 3
3 4
4 2
1 2 1 3
*/
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:79:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int i = 0; i < X.size(); i++){
~~^~~~~~~~~~
werewolf.cpp:95:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int j = 0; j < g[cur].size(); j++){
~~^~~~~~~~~~~~~~~
werewolf.cpp:106:25: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int ii = 0; ii < S.size(); ii++){
~~~^~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
8 ms |
5112 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
8 ms |
5112 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
592 ms |
27572 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
8 ms |
5112 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
