oj.uz

Submission #402066

# Submission time Handle Problem Language Result Execution time Memory
402066 2021-05-11T09:22:44 Z victoriad Library (JOI18_library) C++14
100 / 100
 564 ms 296 KB 
#include <cstdio>
#include <vector>
#include "library.h"
using namespace std;
 
 
void Solve(int N)
{ 
  vector<int>res;
  
  if(N==1){
    res.push_back(1);
  }
  
  else{

    int primero;
    vector<int>l(N,1);
          for(int i=0;i<N;i++){
           l[i]--;
            if(Query(l)==1){
           primero=i;
           res.push_back(primero);
            l[i]++;
            break;
            }
          l[i]++;
          }
         
  vector<bool>c(N,false);
  c[primero]=true;
  while(res.size()<N){
    vector<int>libres;
    for(int i=0;i<N;i++){
      if(!c[i]){
		  libres.push_back(i);
	  }
    }
    int low=0,hi=libres.size();
    while(hi-low>1){
      int mid=(hi+low)/2;
	  l.assign(N,0);
      for(int i=0;i<mid;i++)l[libres[i]]++;
      int v=Query(l);
      l[res.back()]++;
      if(v==Query(l)){
        hi=mid;
      }
      else{
        low=mid;
      }
    }
    res.push_back(libres[low]);
    c[libres[low]]=true;
  }
  for(int i=0;i<N;i++)res[i]++;
  }
  Answer(res);
       
}

Compilation message

library.cpp: In function 'void Solve(int)':
library.cpp:32:19: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   32 |   while(res.size()<N){
      |         ~~~~~~~~~~^~
library.cpp:31:12: warning: 'primero' may be used uninitialized in this function [-Wmaybe-uninitialized]
   31 |   c[primero]=true;
      |            ^

Subtask #1
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 292 KB # of queries: 2375
2 Correct 48 ms 200 KB # of queries: 2409
3 Correct 54 ms 200 KB # of queries: 2648
4 Correct 57 ms 288 KB # of queries: 2595
5 Correct 37 ms 200 KB # of queries: 2508
6 Correct 31 ms 200 KB # of queries: 2551
7 Correct 33 ms 200 KB # of queries: 2544
8 Correct 42 ms 200 KB # of queries: 2420
9 Correct 38 ms 292 KB # of queries: 2546
10 Correct 28 ms 200 KB # of queries: 1474
11 Correct 1 ms 200 KB # of queries: 0
12 Correct 1 ms 200 KB # of queries: 1
13 Correct 1 ms 200 KB # of queries: 4
14 Correct 1 ms 200 KB # of queries: 7
15 Correct 2 ms 200 KB # of queries: 77
16 Correct 2 ms 200 KB # of queries: 183

Subtask #2
81.0 / 81.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 292 KB # of queries: 2375
2 Correct 48 ms 200 KB # of queries: 2409
3 Correct 54 ms 200 KB # of queries: 2648
4 Correct 57 ms 288 KB # of queries: 2595
5 Correct 37 ms 200 KB # of queries: 2508
6 Correct 31 ms 200 KB # of queries: 2551
7 Correct 33 ms 200 KB # of queries: 2544
8 Correct 42 ms 200 KB # of queries: 2420
9 Correct 38 ms 292 KB # of queries: 2546
10 Correct 28 ms 200 KB # of queries: 1474
11 Correct 1 ms 200 KB # of queries: 0
12 Correct 1 ms 200 KB # of queries: 1
13 Correct 1 ms 200 KB # of queries: 4
14 Correct 1 ms 200 KB # of queries: 7
15 Correct 2 ms 200 KB # of queries: 77
16 Correct 2 ms 200 KB # of queries: 183
17 Correct 531 ms 284 KB # of queries: 17982
18 Correct 564 ms 284 KB # of queries: 17293
19 Correct 502 ms 288 KB # of queries: 17467
20 Correct 484 ms 284 KB # of queries: 16325
21 Correct 459 ms 280 KB # of queries: 15324
22 Correct 490 ms 280 KB # of queries: 17669
23 Correct 514 ms 296 KB # of queries: 17224
24 Correct 163 ms 200 KB # of queries: 7915
25 Correct 508 ms 200 KB # of queries: 17136
26 Correct 404 ms 200 KB # of queries: 15963
27 Correct 185 ms 200 KB # of queries: 8040
28 Correct 488 ms 200 KB # of queries: 15957
29 Correct 439 ms 200 KB # of queries: 15939
30 Correct 495 ms 288 KB # of queries: 15957