oj.uz

Submission #341462

# Submission time Handle Problem Language Result Execution time Memory
341462 2020-12-29T19:04:20 Z a_player Werewolf (IOI18_werewolf) C++14
0 / 100
 531 ms 34784 KB 
#include "werewolf.h"
#include <bits/stdc++.h>
#ifdef ALE
#include "grader.cpp"
#endif
#define f first
#define s second
#define debug cout<<"ok"<<endl

using namespace std;

const int nax=2e5+5;

vector<int> grafo[nax];
vector<int> l;
bitset<nax> v;
int f[nax];
int ind[nax];
int pos[nax];
pair<int,int> ans[nax];
int Ni;
void update(int k){
  k++;
  while(k<=Ni){
    f[k]++;
    k+=k&(-k);
  }
}
int query(int k){
  if(k<0)return 0;
  k++;
  int sol=0;
  while(k>0){
    sol+=f[k];
    k-=k&(-k);
  }
  return sol;

}

int leftmost(int u, int v){
  int sol=u-1;
  int q=query(u-1);
  for(int b=v-u;b>=1;b/=2)
  while(sol+b<=v&&query(sol+b)==u)sol+=b;
  return sol+1;
}
int rightmost(int u, int v){
  int sol=v+1;
  int q=query(v);
  for(int b=v-u;b>=1;b/=2)
  while(sol-b>=u&&query(sol-b-1)==q)sol-=b;
  return sol-1;
}



vector<int> check_validity(int N, vector<int> X, vector<int> Y,
                                vector<int> S, vector<int> E,
                                vector<int> L, vector<int> R) {

 Ni=N;
  int Q = S.size();
  int M=X.size();
  vector<int> A(Q);
  int ini=-1;
  for(int i=0;i<M;i++){
    grafo[X[i]].push_back(Y[i]);
    grafo[Y[i]].push_back(X[i]);
  }
  for(int i=0;i<N;i++)
    if(grafo[i].size()==1){
      ini=i;
      break;
  }
  while(ini!=-1){
    v[ini]=1;
    ind[ini]=l.size();
    l.push_back(ini);
    if(!v[grafo[ini][0]])ini=grafo[ini][0];
    else if(grafo[ini].size()>1)ini=grafo[ini][1];
    else ini=-1;
  }
  //-------------
  auto cmpl=[&](int x,int y){
    return L[x]<L[y];
  };
  auto cmpr=[&](int x, int y){
    return R[x]>R[y];
  };
  iota(pos,pos+Q,0);
  sort(pos,pos+Q,cmpl);
  int j=0;
  for(int i=0;i<Q;i++){
    int x=pos[i];
    while(j<N&&j<L[x])update(ind[j++]);
    if(ind[S[x]]<ind[E[x]]){
      ans[i].f=leftmost(ind[S[x]],ind[E[x]]);
    }else ans[i].f=rightmost(ind[E[x]],ind[S[x]]);

  }
  iota(pos,pos+Q,0);
  sort(pos,pos+Q,cmpr);
  for(int i=0;i<=N;i++)f[i]=0;
 j=N-1;
  for(int i=0;i<Q;i++){
    int x=pos[i];
    while(j>=0&&j>R[x])update(ind[j--]);
    if(ind[S[x]]<ind[E[x]]){
      ans[i].s=rightmost(ind[S[x]],ind[E[x]]);
    }else ans[i].s=leftmost(ind[E[x]],ind[S[x]]);

  }
//----------------------------
  for(int q=0;q<Q;q++){
    int s=ind[S[q]],e=ind[E[q]];
    if(s<e){
      if(ans[q].f<ans[q].s)A[q]=0;
      else if(ans[q].s+1==ans[q].f)A[q]=0;
      else A[q]=1;
    }else{
      if(ans[q].f>ans[q].s)A[q]=0;
      else if(ans[q].f+1==ans[q].s)A[q]=0;
      else A[q]=1;
    }
  }
return A;

}

Compilation message

werewolf.cpp: In function 'int leftmost(int, int)':
werewolf.cpp:43:7: warning: unused variable 'q' [-Wunused-variable]
   43 |   int q=query(u-1);
      |       ^

Subtask #1
0 / 7.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 5100 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 5100 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 34.0

# Verdict Execution time Memory Grader output
1 Incorrect 531 ms 34784 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 51.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 5100 KB Output isn't correct
2 Halted 0 ms 0 KB -