oj.uz

Submission #995022

# Submission time Handle Problem Language Result Execution time Memory
995022 2024-06-08T10:44:16 Z TsotneSV Library (JOI18_library) C++14
100 / 100
 367 ms 684 KB 
#pragma gcc diagnostic "-std=c++1z"
#include <bits/stdc++.h>
#include "library.h"
using namespace std;
/* /\_/\
  (= ._.)
  / >  \>
*/

// #define int long long
#define fi first
#define se second
#define pb push_back
#define ins insert
#define mp make_pair
#define send {ios_base::sync_with_stdio(false);}
#define help {cin.tie(0);}
#define endl '\n'
#define sz(x) ((long long) (x).size())
#define all(x) (x).begin(),(x).end()
#define print(x) cout<<(x)<<" ";
#define printl(x) cout<<(x)<<endl
#define dbg(x) cerr<<#x<<" "<<x<<endl

typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<pii> vpi;
typedef vector<pll> vpl;

void fileIO(string filename) {
	freopen((filename + ".in").c_str(), "r", stdin);
	freopen((filename + ".out").c_str(), "w", stdout);
}

// const ll mod = 1000000007;
// const ll mod = 998244353;
// ll mod;

const int inf=1e9,MAXN=2e5+5; 
const ll INF=1e18; 
const ld pi = 3.14159265358979323846;

/* int Query(vector<int> &M) {
  for(int i : M) print(i);
  cout<<endl;
  int q;
  cin>>q;
  return q;
}
void Answer(vector<int>& res) {
  for(int i : res) print(i);
  cout<<endl;
} */

void Solve(int N){

  if(N == 1) {
    vi ans = {1};
    Answer(ans);
    return;
  }

  vector<int> M(N,1),ans;

  for(int i=1;i<=N;i++) {
    M[i-1] = 0;
    int q = Query(M);
    M[i-1] = 1;
    if(q == 1) {
        ans.pb(i);
        break;
    } 
  }

  vi leftover;
  for(int i=1;i<=N;i++) {
    if(i != ans.back()) leftover.pb(i);
  }

  for(int i=2;i<=N;i++) {
    int l = 0,r = sz(leftover) - 1,idx = 0;

    while(l <= r) {
      M = vi(N,0); M[ans.back() - 1] = 1;
      int mid = (l + r)/2;
      for(int j=0;j<=mid;j++) {
        M[leftover[j]-1] = 1;
      }

      int q1 = Query(M);
      M[ans.back() - 1] = 0;
      int q2 = Query(M);
      if(q1 == q2) {
        idx = mid;
        r = mid - 1;
      }else {
        l = mid + 1;
      }
    }

    ans.pb(leftover[idx]);
    leftover.erase(leftover.begin() + idx);
  }

  Answer(ans);

}


/*signed main() {
  Solve(1);  
}*/

Compilation message

library.cpp:1: warning: ignoring '#pragma gcc diagnostic' [-Wunknown-pragmas]
    1 | #pragma gcc diagnostic "-std=c++1z"
      | 
library.cpp: In function 'void fileIO(std::string)':
library.cpp:36:9: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   36 |  freopen((filename + ".in").c_str(), "r", stdin);
      |  ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
library.cpp:37:9: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   37 |  freopen((filename + ".out").c_str(), "w", stdout);
      |  ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 344 KB # of queries: 2401
2 Correct 29 ms 344 KB # of queries: 2437
3 Correct 43 ms 684 KB # of queries: 2658
4 Correct 23 ms 344 KB # of queries: 2597
5 Correct 30 ms 344 KB # of queries: 2526
6 Correct 24 ms 344 KB # of queries: 2565
7 Correct 20 ms 344 KB # of queries: 2556
8 Correct 28 ms 344 KB # of queries: 2424
9 Correct 22 ms 344 KB # of queries: 2550
10 Correct 13 ms 344 KB # of queries: 1488
11 Correct 0 ms 344 KB # of queries: 0
12 Correct 0 ms 344 KB # of queries: 3
13 Correct 0 ms 344 KB # of queries: 6
14 Correct 0 ms 344 KB # of queries: 9
15 Correct 1 ms 344 KB # of queries: 79
16 Correct 1 ms 340 KB # of queries: 195

Subtask #2
81.0 / 81.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 344 KB # of queries: 2401
2 Correct 29 ms 344 KB # of queries: 2437
3 Correct 43 ms 684 KB # of queries: 2658
4 Correct 23 ms 344 KB # of queries: 2597
5 Correct 30 ms 344 KB # of queries: 2526
6 Correct 24 ms 344 KB # of queries: 2565
7 Correct 20 ms 344 KB # of queries: 2556
8 Correct 28 ms 344 KB # of queries: 2424
9 Correct 22 ms 344 KB # of queries: 2550
10 Correct 13 ms 344 KB # of queries: 1488
11 Correct 0 ms 344 KB # of queries: 0
12 Correct 0 ms 344 KB # of queries: 3
13 Correct 0 ms 344 KB # of queries: 6
14 Correct 0 ms 344 KB # of queries: 9
15 Correct 1 ms 344 KB # of queries: 79
16 Correct 1 ms 340 KB # of queries: 195
17 Correct 316 ms 432 KB # of queries: 18030
18 Correct 346 ms 592 KB # of queries: 17279
19 Correct 367 ms 428 KB # of queries: 17479
20 Correct 261 ms 428 KB # of queries: 16301
21 Correct 274 ms 428 KB # of queries: 15352
22 Correct 306 ms 592 KB # of queries: 17663
23 Correct 309 ms 428 KB # of queries: 17250
24 Correct 102 ms 592 KB # of queries: 7917
25 Correct 291 ms 436 KB # of queries: 17158
26 Correct 250 ms 432 KB # of queries: 16003
27 Correct 108 ms 424 KB # of queries: 8046
28 Correct 267 ms 588 KB # of queries: 15975
29 Correct 270 ms 428 KB # of queries: 15957
30 Correct 281 ms 344 KB # of queries: 15975