Submission #374614

#	Time	Username	Problem	Language	Result	Execution time	Memory
374614		mohamedsobhi777	Library (JOI18_library)	C++14	19 / 100	396 ms	388 KiB

library

#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;
                     }
                     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 / 19
• Subtask 2: 0 / 81