oj.uz

답안 #374640

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
374640 2021-03-07T18:27:03 Z mohamedsobhi777 도서관 (JOI18_library) C++14
100 / 100
 354 ms 748 KB 
#include <bits/stdc++.h>
#include <vector>
#include "library.h"
using namespace std;
#define vi vector<int>
#define pb push_back
int n;

struct sub
{
       vi a;
       sub(int x)
       {
              a = {x};
       }
       sub() {}
};

vector<sub> ar;

int query(vi x)
{
       vi ret(n, 0);
       for (auto u : x)
              ret[u] = 1;
       return Query(ret);
}

bool belong(sub x, int y)
{
       x.a.pb(y);
       return query(x.a) == 1;
}

bool belong2(sub x, int y)
{
       if (x.a.empty())
              return 0;
       int z = query(x.a);
       x.a.pb(y);
       return query(x.a) <= z;
}

bool direction(sub x, int u)
{
       vi tmp;
       tmp.pb(x.a.back());
       tmp.pb(u);
       return query(tmp) == 1;
}

void merge(sub &x, int y)
{
       if (direction(x, y) == 1)
       {
              x.a.pb(y);
       }
       else
       {
              vi add = {y};
              x.a.insert(x.a.begin(), add.begin(), add.end());
       }
}

int get(int lo, int hi, int i)
{
       int ans = 0;
       while (lo <= hi)
       {
              int mid = (lo + hi) >> 1;

              vi qu(n, 0);
              for (int j = lo; j <= mid; ++j)
              {
                     for (auto u : ar[j].a)
                            qu[u] = 1;
              }
              int ask1 = Query(qu);
              qu[i] = 1;
              if (Query(qu) == ask1)
              {
                     ans = mid;
                     hi = mid - 1;
              }
              else
                     lo = mid + 1;
       }
       return ans;
}

void Solve(int N)
{
       n = N;
       vi tmp(N, 0);
       int comp = 0;
       for (int i = 0; i < N; ++i)
       {
              tmp[i] = 1;
              int y = Query(tmp);
              if (y == comp + 1)
                     ar.pb(sub(i));
              else if (y == comp)
                     merge(ar[get(0, (int)ar.size() - 1, i)], i);
              else
              {

                     int lo = 0, hi = (int)ar.size() - 1;
                     int ans = 0;
                     while (lo <= hi)
                     {
                            int mid = (lo + hi) >> 1;
                            sub lhs, rhs;
                            bool bl = 0, br = 0;
                            for (int j = 0; j < (int)ar.size(); ++j)
                            {
                                   if (j <= mid)
                                          lhs.a.insert(lhs.a.end(), ar[j].a.begin(), ar[j].a.end());
                                   else
                                          rhs.a.insert(rhs.a.end(), ar[j].a.begin(), ar[j].a.end());
                            }
                            bl = belong2(lhs, i);
                            br = belong2(rhs, i);
                            if (bl && br)
                            {
                                   ans = mid;
                                   break;
                            }
                            if (bl)
                                   hi = mid - 1;
                            else
                                   lo = mid + 1;
                     }

                     vi nei = {get(0, ans, i), get(ans + 1, (int)ar.size() - 1, i)};

                     sub ret;
                     if (!direction(ar[nei[0]], i))
                            reverse(ar[nei[0]].a.begin(), ar[nei[0]].a.end());
                     if (direction(ar[nei[1]], i))
                            reverse(ar[nei[1]].a.begin(), ar[nei[1]].a.end());

                     ret.a.insert(ret.a.end(), ar[nei[0]].a.begin(), ar[nei[0]].a.end());
                     ret.a.pb(i);
                     ret.a.insert(ret.a.end(), ar[nei[1]].a.begin(), ar[nei[1]].a.end());

                     vector<sub> nar;
                     for (int j = 0; j < (int)ar.size(); ++j)
                     {
                            if (j == nei[0] || j == nei[1])
                                   continue;
                            nar.pb(ar[j]);
                     }
                     nar.pb(ret);
                     ar = nar;
              }
              comp = y;
       }

       for (auto &u : ar[0].a)
              ++u;
       Answer(ar[0].a);
}

Subtask #1
19.0 / 19.0

# 결과 실행 시간 메모리 Grader output
1 Correct 39 ms 364 KB # of queries: 2491
2 Correct 36 ms 492 KB # of queries: 2433
3 Correct 39 ms 364 KB # of queries: 2697
4 Correct 43 ms 364 KB # of queries: 2567
5 Correct 38 ms 364 KB # of queries: 2613
6 Correct 45 ms 364 KB # of queries: 2571
7 Correct 47 ms 364 KB # of queries: 2587
8 Correct 35 ms 364 KB # of queries: 2479
9 Correct 43 ms 364 KB # of queries: 2619
10 Correct 20 ms 364 KB # of queries: 1513
11 Correct 0 ms 364 KB # of queries: 1
12 Correct 1 ms 364 KB # of queries: 5
13 Correct 1 ms 364 KB # of queries: 9
14 Correct 1 ms 364 KB # of queries: 17
15 Correct 2 ms 364 KB # of queries: 99
16 Correct 4 ms 364 KB # of queries: 209

Subtask #2
81.0 / 81.0

# 결과 실행 시간 메모리 Grader output
1 Correct 39 ms 364 KB # of queries: 2491
2 Correct 36 ms 492 KB # of queries: 2433
3 Correct 39 ms 364 KB # of queries: 2697
4 Correct 43 ms 364 KB # of queries: 2567
5 Correct 38 ms 364 KB # of queries: 2613
6 Correct 45 ms 364 KB # of queries: 2571
7 Correct 47 ms 364 KB # of queries: 2587
8 Correct 35 ms 364 KB # of queries: 2479
9 Correct 43 ms 364 KB # of queries: 2619
10 Correct 20 ms 364 KB # of queries: 1513
11 Correct 0 ms 364 KB # of queries: 1
12 Correct 1 ms 364 KB # of queries: 5
13 Correct 1 ms 364 KB # of queries: 9
14 Correct 1 ms 364 KB # of queries: 17
15 Correct 2 ms 364 KB # of queries: 99
16 Correct 4 ms 364 KB # of queries: 209
17 Correct 336 ms 492 KB # of queries: 17427
18 Correct 341 ms 748 KB # of queries: 17105
19 Correct 347 ms 580 KB # of queries: 17463
20 Correct 354 ms 620 KB # of queries: 16377
21 Correct 295 ms 492 KB # of queries: 15237
22 Correct 353 ms 628 KB # of queries: 17643
23 Correct 283 ms 640 KB # of queries: 17427
24 Correct 128 ms 492 KB # of queries: 7977
25 Correct 327 ms 492 KB # of queries: 16959
26 Correct 291 ms 500 KB # of queries: 15917
27 Correct 118 ms 508 KB # of queries: 7973
28 Correct 82 ms 492 KB # of queries: 3997
29 Correct 87 ms 364 KB # of queries: 3993
30 Correct 81 ms 364 KB # of queries: 3997