oj.uz

Submission #1003842

# Submission time Handle Problem Language Result Execution time Memory
1003842 2024-06-20T18:52:31 Z AdamGS Library (JOI18_library) C++17
100 / 100
 151 ms 708 KB 
#include "library.h"
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define rep(a, b) for(int a = 0; a < (b); ++a)
#define st first
#define nd second
#define pb push_back
#define all(a) a.begin(), a.end()
void Solve(int n) {
  vector<vector<int>>V;
  V.pb({0});
  for(int i=1; i<n; ++i) {
    vector<int>T(n);
    rep(j, i+1) T[j]=1;
    int a=Query(T);
    if(a>V.size()) {
      V.pb({i});
      continue;
    }
    int po=0, ko=V.size()-1;
    while(po<ko) {
      int sr=(po+ko)/2;
      rep(j, n) T[j]=0;
      rep(j, sr+1) rep(l, V[j].size()) T[V[j][l]]=1;
      T[i]=1;
      int x=Query(T);
      if(x>sr+1) po=sr+1; else ko=sr;
    }
    rep(j, n) T[j]=0;
    T[i]=1;
    T[V[po].back()]=1;
    if(Query(T)==2) reverse(all(V[po]));
    V[po].pb(i);
    if(a==V.size()) continue;
    int b=po;
    po=b+1; ko=V.size()-1;
    while(po<ko) {
      int sr=(po+ko)/2;
      rep(j, n) T[j]=0;
      for(int j=b+1; j<=sr; ++j) rep(l, V[j].size()) T[V[j][l]]=1;
      T[i]=1;
      int x=Query(T);
      if(x>sr-b) po=sr+1; else ko=sr;
    }
    rep(j, n) T[j]=0;
    T[i]=1;
    T[V[po][0]]=1;
    if(Query(T)==2) reverse(all(V[po]));
    for(auto j : V[po]) V[b].pb(j);
    for(int j=po+1; j<V.size(); ++j) V[j-1]=V[j];
    V.pop_back();
  }
  rep(i, V[0].size()) ++V[0][i];
  Answer(V[0]);
}

Compilation message

library.cpp: In function 'void Solve(int)':
library.cpp:17:9: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   17 |     if(a>V.size()) {
      |        ~^~~~~~~~~
library.cpp:5:36: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    5 | #define rep(a, b) for(int a = 0; a < (b); ++a)
      |                                    ^
library.cpp:25:20: note: in expansion of macro 'rep'
   25 |       rep(j, sr+1) rep(l, V[j].size()) T[V[j][l]]=1;
      |                    ^~~
library.cpp:35:9: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   35 |     if(a==V.size()) continue;
      |        ~^~~~~~~~~~
library.cpp:5:36: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    5 | #define rep(a, b) for(int a = 0; a < (b); ++a)
      |                                    ^
library.cpp:41:34: note: in expansion of macro 'rep'
   41 |       for(int j=b+1; j<=sr; ++j) rep(l, V[j].size()) T[V[j][l]]=1;
      |                                  ^~~
library.cpp:51:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   51 |     for(int j=po+1; j<V.size(); ++j) V[j-1]=V[j];
      |                     ~^~~~~~~~~
library.cpp:5:36: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
    5 | #define rep(a, b) for(int a = 0; a < (b); ++a)
      |                                    ^
library.cpp:54:3: note: in expansion of macro 'rep'
   54 |   rep(i, V[0].size()) ++V[0][i];
      |   ^~~

Subtask #1
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 592 KB # of queries: 1267
2 Correct 9 ms 444 KB # of queries: 1262
3 Correct 10 ms 440 KB # of queries: 1336
4 Correct 8 ms 344 KB # of queries: 1341
5 Correct 9 ms 344 KB # of queries: 1313
6 Correct 6 ms 344 KB # of queries: 1327
7 Correct 10 ms 444 KB # of queries: 1329
8 Correct 11 ms 440 KB # of queries: 1241
9 Correct 10 ms 444 KB # of queries: 1339
10 Correct 6 ms 440 KB # of queries: 776
11 Correct 1 ms 344 KB # of queries: 0
12 Correct 0 ms 344 KB # of queries: 2
13 Correct 1 ms 344 KB # of queries: 4
14 Correct 1 ms 344 KB # of queries: 7
15 Correct 1 ms 344 KB # of queries: 49
16 Correct 1 ms 344 KB # of queries: 115

Subtask #2
81.0 / 81.0

# Verdict Execution time Memory Grader output
1 Correct 10 ms 592 KB # of queries: 1267
2 Correct 9 ms 444 KB # of queries: 1262
3 Correct 10 ms 440 KB # of queries: 1336
4 Correct 8 ms 344 KB # of queries: 1341
5 Correct 9 ms 344 KB # of queries: 1313
6 Correct 6 ms 344 KB # of queries: 1327
7 Correct 10 ms 444 KB # of queries: 1329
8 Correct 11 ms 440 KB # of queries: 1241
9 Correct 10 ms 444 KB # of queries: 1339
10 Correct 6 ms 440 KB # of queries: 776
11 Correct 1 ms 344 KB # of queries: 0
12 Correct 0 ms 344 KB # of queries: 2
13 Correct 1 ms 344 KB # of queries: 4
14 Correct 1 ms 344 KB # of queries: 7
15 Correct 1 ms 344 KB # of queries: 49
16 Correct 1 ms 344 KB # of queries: 115
17 Correct 96 ms 440 KB # of queries: 8901
18 Correct 102 ms 444 KB # of queries: 8807
19 Correct 113 ms 704 KB # of queries: 8825
20 Correct 99 ms 708 KB # of queries: 8325
21 Correct 81 ms 428 KB # of queries: 7822
22 Correct 151 ms 692 KB # of queries: 8913
23 Correct 98 ms 596 KB # of queries: 8902
24 Correct 44 ms 600 KB # of queries: 4080
25 Correct 128 ms 684 KB # of queries: 8706
26 Correct 98 ms 692 KB # of queries: 8118
27 Correct 41 ms 448 KB # of queries: 4068
28 Correct 25 ms 600 KB # of queries: 1998
29 Correct 24 ms 436 KB # of queries: 1996
30 Correct 25 ms 432 KB # of queries: 1998