oj.uz

Submission #374607

# Submission time Handle Problem Language Result Execution time Memory
374607 2021-03-07T15:04:34 Z mohamedsobhi777 Library (JOI18_library) C++14
19 / 100
 345 ms 492 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)
              {
                     for (auto &u : ar)
                     {
                            if (belong(u, i))
                            {
                                   merge(u, i);
                                   break;
                            }
                     }
              }
              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 54 ms 364 KB # of queries: 3730
2 Correct 45 ms 492 KB # of queries: 3568
3 Correct 63 ms 364 KB # of queries: 3930
4 Correct 55 ms 492 KB # of queries: 3812
5 Correct 54 ms 364 KB # of queries: 3674
6 Correct 57 ms 364 KB # of queries: 3544
7 Correct 52 ms 364 KB # of queries: 3735
8 Correct 51 ms 364 KB # of queries: 3518
9 Correct 58 ms 364 KB # of queries: 3950
10 Correct 31 ms 364 KB # of queries: 1734
11 Correct 0 ms 364 KB # of queries: 1
12 Correct 1 ms 364 KB # of queries: 4
13 Correct 1 ms 364 KB # of queries: 7
14 Correct 1 ms 364 KB # of queries: 10
15 Correct 1 ms 364 KB # of queries: 55
16 Correct 2 ms 364 KB # of queries: 128

Subtask #2
0 / 81.0

# Verdict Execution time Memory Grader output
1 Correct 54 ms 364 KB # of queries: 3730
2 Correct 45 ms 492 KB # of queries: 3568
3 Correct 63 ms 364 KB # of queries: 3930
4 Correct 55 ms 492 KB # of queries: 3812
5 Correct 54 ms 364 KB # of queries: 3674
6 Correct 57 ms 364 KB # of queries: 3544
7 Correct 52 ms 364 KB # of queries: 3735
8 Correct 51 ms 364 KB # of queries: 3518
9 Correct 58 ms 364 KB # of queries: 3950
10 Correct 31 ms 364 KB # of queries: 1734
11 Correct 0 ms 364 KB # of queries: 1
12 Correct 1 ms 364 KB # of queries: 4
13 Correct 1 ms 364 KB # of queries: 7
14 Correct 1 ms 364 KB # of queries: 10
15 Correct 1 ms 364 KB # of queries: 55
16 Correct 2 ms 364 KB # of queries: 128
17 Runtime error 345 ms 492 KB Execution killed with signal 13
18 Halted 0 ms 0 KB -