Submission #982492

#	Time	Username	Problem	Language	Result	Execution time	Memory
982492		wood	Werewolf (IOI18_werewolf)	C++17	0 / 100	167 ms	36420 KiB

werewolf

#include <bits/stdc++.h>  
using namespace std;
 
typedef long long ll;
typedef pair<int,int> p32;
typedef pair<ll,ll> p64;
#define pb push_back
#define eb emplace_back
#define fi first
#define se second
#define vi vector<int>
#define vp32 vector<p32>
#define fast_cin() ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL)
#define MOD %1000000007
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
template <class T>
using Tree =
    tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
//never guess
//never debug without reviewing code
//never try adding ones or substracting them
//only step by step debug when necessay

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){
    int m = X.size(), q =S.size();
    //turn graph into array 
    vi adj[N];
    for(int i = 0; i<m; i++){
        adj[X[i]-1].pb(Y[i]-1);
        adj[Y[i]-1].pb(X[i]-1);
    }
    vi arr;
    int inds[N];
    for (size_t i = 0; i < N; i++)
    {
        if(adj[i].size()==1){
            int cur = i, prev = i;
            arr.pb(i);
            inds[i] = arr.size();
            while(arr.size()<N)
            for(int x : adj[cur]){
                if(x!=prev){
                    prev = cur;
                    cur = x;
                    arr.pb(x);
                    inds[x] = arr.size();
                }
            }
            break;
        }
    }
    //split intervals into forwards and backwards
    using t = tuple<int,int,int>;
    vector<t> forw, back;
    for (size_t i = 0; i < q; i++)
    {
        if(inds[S[i]-1]<inds[E[i]-1]) forw.eb(S[i]-1,E[i]-1,i);
        else back.eb(S[i]-1,E[i]-1,i);
    }
    //sort forw and back depending on their start position
    sort(forw.begin(),forw.end(),[&](t l, t r){return inds[get<0>(l)]<inds[get<0>(r)];});
    sort(back.begin(),back.end(),[&](t l, t r){return inds[get<1>(l)]<inds[get<1>(r)];});
    //for forw look for the first instance bigger than r for back look at the first instance smaller than l
    p32 res[q];
    priority_queue<p32> l,r;
    auto f = forw.begin(), b = back.begin();
    for (size_t j = 0; j < N; j++)
    {
        int i = arr[j];
        while(f!=forw.end()&&get<0>(*f)==i){
            r.emplace(-R[get<2>(*f)],get<2>(*f));
            f++;
        }
        while(b!=back.end()&&get<1>(*b)==i){
            l.emplace(L[get<2>(*b)],get<2>(*b));
            b++;
        }
        while(!r.empty()&&i>-r.top().fi-1){
            res[r.top().se].se = j-1;
            r.pop();
        }
        while(!l.empty()&&i<l.top().fi-1){
            res[l.top().se].se = j-1;
            l.pop();
        }
    }
    //empty both queues
    while(!r.empty()){
        res[r.top().se].se = INT_MAX;
        r.pop();
    }
    while(!l.empty()){
        res[l.top().se].se = INT_MAX;
        l.pop();
    }
    //sort forw and back depending on their end position
    sort(forw.begin(),forw.end(),[&](t l, t r){return inds[get<1>(l)]<inds[get<1>(r)];});
    sort(back.begin(),back.end(),[&](t l, t r){return inds[get<0>(l)]<inds[get<0>(r)];});
    //do the opposite: first instance smaller than l for forw and first instance bigger than r for back
    auto rf = forw.rbegin(), rb = back.rbegin();
    for (int j = N - 1; j >= 0; j--)
    {
        int i = arr[j];
        while(rf!=forw.rend()&&get<1>(*rf)==i){
            l.emplace(L[get<2>(*rf)],get<2>(*rf));
            rf++;
        }
        while(rb!=back.rend()&&get<0>(*rb)==i){
            r.emplace(-R[get<2>(*rb)],get<2>(*rb));
            rb++;
        }
        while(!r.empty()&&i>-r.top().fi-1){
            res[r.top().se].fi = j+1;
            r.pop();
        }
        while(!l.empty()&&i<l.top().fi-1){
            res[l.top().se].fi = j+1;
            l.pop();
        }
    }
    while(!r.empty()){
        res[r.top().se].fi = INT_MIN;
        r.pop();
    }
    while(!l.empty()){
        res[l.top().se].fi = INT_MIN;
        l.pop();
    }
    vi result;
    for (size_t i = 0; i < q; i++)
        result.pb(res[i].se>=min(S[i],E[i])-1&&res[i].fi<=max(S[i],E[i])-1&&res[i].fi<=res[i].se);
    return result;
}

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:35:26: warning: comparison of integer expressions of different signedness: 'size_t' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   35 |     for (size_t i = 0; i < N; i++)
      |                        ~~^~~
werewolf.cpp:41:29: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   41 |             while(arr.size()<N)
      |                   ~~~~~~~~~~^~
werewolf.cpp:56:26: warning: comparison of integer expressions of different signedness: 'size_t' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   56 |     for (size_t i = 0; i < q; i++)
      |                        ~~^~~
werewolf.cpp:68:26: warning: comparison of integer expressions of different signedness: 'size_t' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   68 |     for (size_t j = 0; j < N; j++)
      |                        ~~^~~
werewolf.cpp:131:26: warning: comparison of integer expressions of different signedness: 'size_t' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
  131 |     for (size_t i = 0; i < q; i++)
      |                        ~~^~~

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