Submission #75874

#TimeUsernameProblemLanguageResultExecution timeMemory
75874Osama_AlkhodairyWerewolf (IOI18_werewolf)C++17
0 / 100
316 ms28016 KiB
#include <bits/stdc++.h> #include "werewolf.h" using namespace std; const int maxn = 200001; int ind[maxn], tree[4 * maxn][2][2]; vector <int> b[maxn], v[maxn], ret; void update(int l, int r, int node, int ind, int val, int idx){ if(r < l) return; if(r < ind || l > ind) return; if(l == r){ tree[node][0][idx] = tree[node][1][idx] = val; return; } int mid = (l + r) / 2; update(l, mid, 2 * node, ind, val, idx); update(mid + 1, r, 2 * node + 1, ind, val, idx); tree[node][0][idx] = min(tree[2 * node][0][idx], tree[2 * node + 1][0][idx]); tree[node][1][idx] = max(tree[2 * node][1][idx], tree[2 * node + 1][1][idx]); } int query(int l, int r, int node, int s, int e, int mx, int idx){ if(r < l) return (mx == 0 ? 1e9 : -1); if(r < s || l > e) return (mx == 0 ? 1e9 : -1); if(s <= l && r <= e) return tree[node][mx][idx]; int mid = (l + r) / 2; if(mx) return max(query(l, mid, 2 * node, s, e, mx, idx), query(mid + 1, r, 2 * node + 1, s, e, mx, idx)); return min(query(l, mid, 2 * node, s, e, mx, idx), query(mid + 1, r, 2 * node + 1, s, e, mx, idx)); } vector <int> check_validity(int N, vector <int> X, vector <int> Y, vector <int> S, vector <int> E, vector <int> L, vector <int> R) { for(int i = 0 ; i < X.size() ; i++){ v[X[i]].push_back(Y[i]); v[Y[i]].push_back(X[i]); } int start[2] = {-1, -1}; for(int i = 0 ; i < N ; i++) if(v[i].size() == 1){ if(start[0] == -1) start[0] = i; else start[1] = i; } // if(start[0] == -1 || start[1] == -1) while(1); /* b[0].push_back(start[0]); b[0].push_back(v[start[0]][0]); while(b[0].size() != N){ int f = v[b[0].back()][0], s = v[b[0].back()][1]; b[0].push_back(f + s - b[0][b[0].size() - 2]); } b[1].push_back(start[1]); b[1].push_back(v[start[1]][0]); for(int i = 1 ; i <= N - 2 ; i++){ // int f = v[b[1].back()][0], s = v[b[1].back()][1]; int f = 1, s = 2; //b[1].push_back(f + s - b[1][b[1].size() - 2]); b[1].push_back(1); }*/ // for(int i = 0 ; i < N ; i++) // b[0].push_back(i); for(int i = 0 ; i < N ; i++) b[1].push_back(i); for(int i = 0 ; i < N ; i++){ // update(0, N - 1, 1, i, b[0][i], 0); // update(0, N - 1, 1, i, b[1][i], 1); } for(int i = 0 ; i < b[0].size() ; i++) ind[b[0][i]] = i; for(int i = 0 ; i < S.size() ; i++){ int s = S[i], e = E[i]; if(s == e){ if(s >= L[i] && s <= R[i]) ret.push_back(1); else ret.push_back(0); continue; } s = ind[s]; e = ind[e]; vector <int> &a = b[0]; int idx = 0; if(e < s){ a = b[1]; idx = 1; s = N - s - 1; e = N - e - 1; } int l = s, r = e; /* while(l <= r){ int mid = (l + r) / 2; if(query(0, N - 1, 1, l, mid, 0, idx) >= L[i]) l = mid + 1; else r = mid - 1; } */ int y = r + 1; l = s, r = e; /* while(l <= r){ int mid = (l + r) / 2; if(query(0, N - 1, 1, mid, r, 1, idx) <= R[i]) r = mid - 1; else l = mid + 1; } */ int x = l - 1; x++; y--; if(x <= y) ret.push_back(1); else ret.push_back(0); } 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:34:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 0 ; i < X.size() ; i++){
                     ~~^~~~~~~~~~
werewolf.cpp:75:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 0 ; i < b[0].size() ; i++)
                     ~~^~~~~~~~~~~~~
werewolf.cpp:77:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 0 ; i < S.size() ; i++){
                     ~~^~~~~~~~~~
werewolf.cpp:87:13: warning: variable 'idx' set but not used [-Wunused-but-set-variable]
         int idx = 0;
             ^~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...