제출 #295587

#제출 시각아이디문제언어결과실행 시간메모리
295587eohomegrownapps늑대인간 (IOI18_werewolf)C++14
0 / 100
509 ms71800 KiB
#include "werewolf.h" #include <bits/stdc++.h> using namespace std; vector<int> l; vector<int> r; int n,q; int sqrtq; vector<vector<int>> adjlist; bool comp(int a, int b){ if (l[a]/sqrtq == l[b]/sqrtq){ return r[a]<r[b]; } else { return l[a]<l[b]; } } 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) { q = s.size(); l=L;r=R;n=N; sqrtq=sqrt(q); vector<int> inds(q); for (int i = 0; i<q; i++){ inds[i]=i; } sort(inds.begin(),inds.end(),comp); /*for (int i : inds){ cout<<l[i]<<' '<<r[i]<<'\n'; }*/ adjlist.resize(n); for (int i = 0; i<x.size(); i++){ //cout<<x[i]<<' '<<y[i]<<endl; adjlist[x[i]].push_back(y[i]); adjlist[y[i]].push_back(x[i]); } int start = -1; for (int i = 0; i<n; i++){ if (adjlist[i].size()==1){ start=i; break; } } int cur = start; int pre = -1; int ptr = 0; int ind2pop[200000]; int pop2ind[200000]; do { ind2pop[ptr]=cur; pop2ind[cur]=ptr; if (adjlist[cur][0]==pre){ pre=cur; cur=adjlist[cur][1]; } else { pre=cur; cur=adjlist[cur][0]; } ptr++; } while (adjlist[cur].size()!=1); ind2pop[ptr]=cur; pop2ind[cur]=ptr; vector<int> ans(q); /*for (int i : ind2pop){ cout<<i<<' '; }cout<<'\n';*/ int lv = 0; int rv = n-1; set<int> lvals; set<int> rvals; /*for (int i = 1; i<n; i++){ rvals.insert(pop2ind[i]); }*/ lvals.insert(-1); lvals.insert(n); rvals.insert(-1); rvals.insert(n); vector<set<int>::iterator> v(n); for (int i = 0; i<q; i++){ int lii = l[inds[i]]; if (lv<lii){ while (lv<lii){ v[pop2ind[lv]]=lvals.insert(pop2ind[lv]).first; lv++; } lv--; } else if (lv>lii){ while (lv>=lii){ lvals.erase(v[pop2ind[lv]]); lv--; } lv++; } int rii = r[inds[i]]; if (rv<rii){ while (rv<=rii){ rvals.erase(v[pop2ind[lv]]); rv++; } rv--; } else if (rv>rii){ while (rv>rii){ v[pop2ind[lv]]=rvals.insert(pop2ind[rv]).first; rv--; } rv++; } /*cout<<"indices in l: "; for (int i : lvals){ cout<<i<<' '; }cout<<'\n'; cout<<"indices in r: "; for (int i : rvals){ cout<<i<<' '; }cout<<'\n';*/ auto lb1 = lvals.lower_bound(pop2ind[s[inds[i]]]); int ls = *(prev(lb1,1)); int le = *lb1; auto lb2 = rvals.lower_bound(pop2ind[e[inds[i]]]); int rs = *(prev(lb2,1)); int re = *(lb2); if (le<rs||re<ls){ ans[inds[i]]=0; } else { ans[inds[i]]=1; } } return ans; }

컴파일 시 표준 에러 (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:38:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   38 |     for (int i = 0; i<x.size(); i++){
      |                     ~^~~~~~~~~
werewolf.cpp:54:9: warning: variable 'ind2pop' set but not used [-Wunused-but-set-variable]
   54 |     int ind2pop[200000];
      |         ^~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...