oj.uz

Submission #598367

# Submission time Handle Problem Language Result Execution time Memory
598367 2022-07-18T07:38:25 Z Dremix10 Werewolf (IOI18_werewolf) C++17
34 / 100
 792 ms 43172 KB 
#include "werewolf.h"
#include <iostream>
#include <assert.h>
#include <numeric>
#include <algorithm>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
typedef pair<int,int> pi;
typedef pair<ll,ll> pl;
#define F first
#define S second
#define endl '\n'
#define all(x) (x).begin(),(x).end()
#define sz(x) (int)(x).size()
#ifdef dremix
    #define p(x) cerr<<#x<<" = "<<x<<endl;
    #define p2(x,y) cerr<<#x<<" , "<<#y<<" = "<<x<<" , "<<y<<endl;
    #define pp(x) cerr<<#x<<" = ("<<x.F<<" , "<<x.S<<")"<<endl;
    #define pv(x) cerr<<#x<<" = {";for(auto u : x)cerr<<u<<", ";cerr<<"}"<<endl;
    #define ppv(x) cerr<<#x<<" = {";for(auto u : x)cerr<<u.F<<"-"<<u.S<<", ";cerr<<"}"<<endl;
#else
    #define p(x) {}
    #define p2(x,y) {}
    #define pp(x) {}
    #define pv(x) {}
    #define ppv(x) {}
#endif
#define fastio ios_base::sync_with_stdio(false);cin.tie(nullptr);
const int maxp = 22;
const ld EPS = 1e-18;
const ll INF = 2e18;
const int MOD = 1e9+7;
const int NN = 3e5+1;


vector<vector<int> > a;
bool flag;



int mn[2][NN*4],mx[2][NN*4];
int arr[2][NN],posi[2][NN];
bool mt = false;

void buildmn(int s, int e, int idx){
    if(s==e){
        mn[mt][idx] = arr[mt][s];
        return;
    }
    int mid = (s+e)/2;
    buildmn(s,mid,idx*2);
    buildmn(mid+1,e,idx*2+1);
    mn[mt][idx] = min(mn[mt][idx*2],mn[mt][idx*2+1]);
}

void buildmx(int s, int e, int idx){
    if(s==e){
        mx[mt][idx] = arr[mt][s];
        return;
    }
    int mid = (s+e)/2;
    buildmx(s,mid,idx*2);
    buildmx(mid+1,e,idx*2+1);
    mx[mt][idx] = max(mx[mt][idx*2],mx[mt][idx*2+1]);
}

int lo(int s, int e, int idx, int l, int x){
    if(e < l)return -1;
    if(s==e){
        assert(mn[mt][idx] < x);
        return s;
    }
    
    int mid = (s+e)/2;
    int res = -1;
    if(mn[mt][idx*2] < x){
        res = lo(s,mid,idx*2,l,x);
    }

    if(res == -1 && mn[mt][idx*2+1] < x){
        res = lo(mid+1,e,idx*2+1,l,x);
    }
    return res;
}

int hi(int s, int e, int idx, int l, int x){
    if(e < l)return -1;
    if(s == e){
        assert(mx[mt][idx] > x);
        return s;
    }

    int mid = (s+e)/2;
    int res = -1;
    if(mx[mt][idx*2] > x){
        res = hi(s,mid,idx*2,l,x);
    }

    if(res == -1 && mx[mt][idx*2+1] > x){
        res = hi(mid+1,e,idx*2+1,l,x);
    }
    return res;
}


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) {

    //arr.resize(N);
    a.assign(N,vector<int>());
    
    int q = S.size();
    int m = X.size();

    int i,k;

    for(i=0;i<m;i++){
        int x = X[i], y = Y[i];
        a[x].push_back(y);
        a[y].push_back(x);
    }

    int x = -1;
    for(i=0;i<N;i++){
        if(a[i].size() == 1)x = i;
    }
    assert(x != -1);
    assert(mt == false);
    
    arr[mt][0] = x;
    int y = x;
    x = a[x][0];
    for(i=1;i<N-1;i++){
        arr[mt][i] = x;
        if(a[x][0] == y){
            y = x;
            x = a[x][1];
        }
        else{
            y = x;
            x = a[x][0];
        }
    }
    arr[mt][N-1] = x;
    assert(a[x].size()==1);

    for(i=0;i<N;i++){
        arr[mt^1][i] = arr[mt][N-i-1];
        cerr<<arr[mt][i]<<" ";
        posi[mt][arr[mt][i]] = i;
    }

    for(i=0;i<N;i++){
        posi[mt^1][arr[mt^1][i]] = i;
    }
    
    cout<<endl;
    vector<int> ans;

    buildmx(0,N-1,1);
    buildmn(0,N-1,1);


    mt ^= 1;
    //reverse(all(arr));

    buildmx(0,N-1,1);
    buildmn(0,N-1,1);

    mt ^= 1;
    //reverse(all(arr));
    

    for(k=0;k<q;k++){
        int s = S[k], e = E[k];
        int l = L[k];
        int r = R[k];

        if(posi[mt][s] > posi[mt][e])
            mt ^= 1;
       
        p(mt)
        p2(posi[mt][s],posi[mt][e])
        int idx = lo(0,N-1,1,posi[mt][s],l);
        
        p(idx)
        if(idx == -1 || idx > posi[mt][e]){
            ans.push_back(true);
            continue;
        }

        if(arr[mt][idx-1] > r){
            ans.push_back(false);
            continue;
        }

        idx = hi(0,N-1,1,idx,r);

        p2(2,idx)
        if(idx == -1 || idx > posi[mt][e]){
            ans.push_back(true);
//           continue;
        }
        else{
            ans.push_back(false);
        }

    }


    return ans;
}

Subtask #1
0 / 7.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 468 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 468 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #3
34.0 / 34.0

# Verdict Execution time Memory Grader output
1 Correct 781 ms 34416 KB Output is correct
2 Correct 686 ms 42848 KB Output is correct
3 Correct 691 ms 42900 KB Output is correct
4 Correct 703 ms 43052 KB Output is correct
5 Correct 715 ms 42892 KB Output is correct
6 Correct 792 ms 43016 KB Output is correct
7 Correct 782 ms 43016 KB Output is correct
8 Correct 694 ms 42948 KB Output is correct
9 Correct 679 ms 43168 KB Output is correct
10 Correct 675 ms 42980 KB Output is correct
11 Correct 739 ms 43020 KB Output is correct
12 Correct 761 ms 43172 KB Output is correct
13 Correct 698 ms 42924 KB Output is correct
14 Correct 735 ms 42892 KB Output is correct
15 Correct 697 ms 42852 KB Output is correct
16 Correct 683 ms 42864 KB Output is correct
17 Correct 736 ms 42832 KB Output is correct

Subtask #4
0 / 51.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 468 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -