oj.uz

Submission #374613

# Submission time Handle Problem Language Result Execution time Memory
374613 2021-03-07T15:19:30 Z mohamedsobhi777 Library (JOI18_library) C++14
19 / 100
 378 ms 620 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());
       }
}

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)
              {
                     int lo = 0, hi = (int)ar.size() - 1;
                     int ans = 0;
                     while (lo <= hi)
                     {
                            int mid = (lo + hi) >> 1;

                            vi qu(N, 0);
                            for (int j = 0; 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;
                     }
                     assert(belong(ar[ans], i));
                     merge(ar[ans], i);
              }
              else
              {
                     vi nei;
                     for (int j = 0; j < (int)ar.size(); ++j)
                     {
                            if (belong(ar[j], i))
                            {
                                   nei.pb(j);
                            }
                     }

                     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;
                     // solve2();
              }
              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 46 ms 364 KB # of queries: 3215
2 Correct 41 ms 620 KB # of queries: 3073
3 Correct 47 ms 492 KB # of queries: 3327
4 Correct 44 ms 492 KB # of queries: 3151
5 Correct 54 ms 492 KB # of queries: 3283
6 Correct 49 ms 364 KB # of queries: 3132
7 Correct 48 ms 492 KB # of queries: 3131
8 Correct 45 ms 364 KB # of queries: 2954
9 Correct 35 ms 376 KB # of queries: 3403
10 Correct 17 ms 376 KB # of queries: 1643
11 Correct 0 ms 364 KB # of queries: 1
12 Correct 0 ms 364 KB # of queries: 6
13 Correct 1 ms 364 KB # of queries: 11
14 Correct 1 ms 364 KB # of queries: 12
15 Correct 1 ms 364 KB # of queries: 67
16 Correct 3 ms 364 KB # of queries: 165

Subtask #2
0 / 81.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 364 KB # of queries: 3215
2 Correct 41 ms 620 KB # of queries: 3073
3 Correct 47 ms 492 KB # of queries: 3327
4 Correct 44 ms 492 KB # of queries: 3151
5 Correct 54 ms 492 KB # of queries: 3283
6 Correct 49 ms 364 KB # of queries: 3132
7 Correct 48 ms 492 KB # of queries: 3131
8 Correct 45 ms 364 KB # of queries: 2954
9 Correct 35 ms 376 KB # of queries: 3403
10 Correct 17 ms 376 KB # of queries: 1643
11 Correct 0 ms 364 KB # of queries: 1
12 Correct 0 ms 364 KB # of queries: 6
13 Correct 1 ms 364 KB # of queries: 11
14 Correct 1 ms 364 KB # of queries: 12
15 Correct 1 ms 364 KB # of queries: 67
16 Correct 3 ms 364 KB # of queries: 165
17 Runtime error 378 ms 364 KB Execution killed with signal 13
18 Halted 0 ms 0 KB -