Submission #75685

#	Time	Username	Problem	Language	Result	Execution time	Memory
75685		Osama_Alkhodairy	Werewolf (IOI18_werewolf)	C++17	0 / 100	330 ms	28960 KiB

werewolf

#include <bits/stdc++.h>
#include "werewolf.h"
using namespace std;

const int N = 200001;

int ind[N], tree[4 * N][2][2];
vector <int> b[2], v[N], 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]);
    while(b[1].size() != N){
        int f = v[b[1].back()][0], s = v[b[1].back()][1];
        b[1].push_back(f + s - b[1][b[1].size() - 2]);
    }
    cout << "b0: "; for(int i : b[0]) cout << i << " "; cout << endl;
    cout << "b1: "; for(int i : b[1]) cout << i << " "; cout << endl;
    */

    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:49:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     while(b[0].size() != N){
           ~~~~~~~~~~~~^~~~
werewolf.cpp:68:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 0 ; i < b[0].size() ; i++)
                     ~~^~~~~~~~~~~~~
werewolf.cpp:70:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 0 ; i < S.size() ; i++){
                     ~~^~~~~~~~~~
werewolf.cpp:80:13: warning: variable 'idx' set but not used [-Wunused-but-set-variable]
         int idx = 0;
             ^~~

• Subtask 1: 0 / 7
• Subtask 2: 0 / 8
• Subtask 3: 0 / 34
• Subtask 4: 0 / 51