oj.uz

Submission #282702

# Submission time Handle Problem Language Result Execution time Memory
282702 2020-08-24T18:55:13 Z sckmd Library (JOI18_library) C++14
0 / 100
 2000 ms 384 KB 
#include <bits/stdc++.h>
#include "library.h"
#define MAX 1005
using namespace std;

//int Query(const std::vector<int>& M);
//void Answer(const std::vector<int>& res);

vector <int> susedi[MAX];
int n;

void go(int idx)
{
  vector <int> all;
  for(int i = 0; i < n; i++)
  {
    if(i == idx)continue;
    if(find(susedi[i].begin(),susedi[i].end(),idx)!=susedi[i].end())continue;
    if(find(susedi[idx].begin(),susedi[idx].end(),i)!=susedi[idx].end())continue;
    if(susedi[i].size()==2)continue;
    all.push_back(i);
  }
  vector <int> qq;
  for(int i = 0; i < n; i++)qq.push_back(0);
  int lo = 0,hi=all.size()-1,mid=lo+hi>>1,r=-1;
  while(lo <= hi)
  {
    for(int j = 0; j < n; j++)qq[j]=0;
    for(int j = lo; j <= mid; j++)
    {
      qq[all[j]]=1;
    }
    int qres = Query(qq);
    qq[idx]=1;
    int qres2 = Query(qq);
    if(qres2 <= qres)r=mid,hi=mid-1;
    else lo=mid+1;
    mid=lo+hi>>1;
  }
  if(r!=-1)susedi[idx].push_back(r),susedi[r].push_back(idx);
}

vector <int> resenje;

void dfs(int v,int p)
{
  resenje.push_back(v);
  for(auto x:susedi[v])
  {
    if(x==p)continue;
    dfs(x,v);
  }
}

void Solve(int N)
{
  n=N;
  for(int i = 0; i < n; i++)
  {
    if(susedi[i].size()<2)go(i);
  }
  for(int i = 0; i < n; i++)
  {
    if(susedi[i].size()==1){dfs(i,-1);break;}
  }
  if(resenje.size()<=n/2)while(1);
  Answer(resenje);
}

Compilation message

library.cpp: In function 'void go(int)':
library.cpp:25:36: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   25 |   int lo = 0,hi=all.size()-1,mid=lo+hi>>1,r=-1;
      |                                  ~~^~~
library.cpp:38:11: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   38 |     mid=lo+hi>>1;
      |         ~~^~~
library.cpp: In function 'void Solve(int)':
library.cpp:66:20: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   66 |   if(resenje.size()<=n/2)while(1);
      |      ~~~~~~~~~~~~~~^~~~~

Subtask #1
0 / 19.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3027 ms 384 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #2
0 / 81.0

# Verdict Execution time Memory Grader output
1 Execution timed out 3027 ms 384 KB Time limit exceeded
2 Halted 0 ms 0 KB -