oj.uz

Submission #374626

# Submission time Handle Problem Language Result Execution time Memory
374626 2021-03-07T16:20:57 Z mohamedsobhi777 Library (JOI18_library) C++14
19 / 100
 406 ms 512 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 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)
                                          bl |= belong(ar[j], i);
                                   else
                                          br |= belong(ar[j], 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)
       // {
       //        for (auto v : u.a)
       //               cout << ++v << " ";
       //        cout << "\n";
       // }

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

Subtask #1
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 80 ms 492 KB # of queries: 5774
2 Correct 75 ms 364 KB # of queries: 5371
3 Correct 112 ms 492 KB # of queries: 7094
4 Correct 71 ms 492 KB # of queries: 5659
5 Correct 81 ms 512 KB # of queries: 6340
6 Correct 86 ms 364 KB # of queries: 5997
7 Correct 87 ms 364 KB # of queries: 6110
8 Correct 109 ms 364 KB # of queries: 5906
9 Correct 92 ms 492 KB # of queries: 6735
10 Correct 61 ms 364 KB # of queries: 3126
11 Correct 1 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: 15
15 Correct 2 ms 364 KB # of queries: 97
16 Correct 5 ms 384 KB # of queries: 227

Subtask #2
0 / 81.0

# Verdict Execution time Memory Grader output
1 Correct 80 ms 492 KB # of queries: 5774
2 Correct 75 ms 364 KB # of queries: 5371
3 Correct 112 ms 492 KB # of queries: 7094
4 Correct 71 ms 492 KB # of queries: 5659
5 Correct 81 ms 512 KB # of queries: 6340
6 Correct 86 ms 364 KB # of queries: 5997
7 Correct 87 ms 364 KB # of queries: 6110
8 Correct 109 ms 364 KB # of queries: 5906
9 Correct 92 ms 492 KB # of queries: 6735
10 Correct 61 ms 364 KB # of queries: 3126
11 Correct 1 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: 15
15 Correct 2 ms 364 KB # of queries: 97
16 Correct 5 ms 384 KB # of queries: 227
17 Runtime error 406 ms 364 KB Execution killed with signal 13
18 Halted 0 ms 0 KB -