oj.uz

Submission #230368

# Submission time Handle Problem Language Result Execution time Memory
230368 2020-05-09T18:21:18 Z muhammad_hokimiyon Library (JOI18_library) C++14
100 / 100
 465 ms 632 KB 
#include <bits/stdc++.h>
#include "library.h"
 
#define fi first
#define se second
#define ll long long
#define dl double long
 
using namespace std;
 
const int maxn = 1e3 + 7;
 
int n;
int p[maxn];
int sz[maxn];
vector < int > g[maxn];
 
int get( int x )
{
    return (p[x] == x ? x : p[x] = get(p[x]));
}
 
void merg( vector < int > &a1 ,  vector < int > &b1 )
{
    for( auto x : b1 )a1.push_back(x);
    b1.clear();
}
 
void meg( int x , int y )
{
    x = get(x);
    y = get(y);
    if( x == y )return;
    if( sz[x] < sz[y] )swap( x , y );
    sz[x] += sz[y];
    p[y] = x;
    vector < int > M(n , 0);
    M[g[x][0] - 1] = 1;
    M[g[y][0] - 1] = 1;
    int x1 = Query( M );
    if( x1 == 1 ){
        reverse( g[x].begin() , g[x].end() );
        merg( g[x] , g[y] );
        return;
    }
    M[g[y][0] - 1] = 0;
    reverse( g[y].begin() , g[y].end() );
    M[g[y][0] - 1] = 1;
    x1 = Query( M );
    if( x1 == 1 ){
        reverse( g[x].begin() , g[x].end() );
        merg( g[x] , g[y] );
        return;
    }
    M[g[x][0] - 1] = 0;
    M[g[x].back() - 1] = 1;
    x1 = Query( M );
    if( x1 == 1 ){
        merg( g[x] , g[y] );
        return;
    }
    reverse( g[y].begin() , g[y].end() );
    merg( g[x] , g[y] );
}
 
void Solve(int n1)
{
    n = n1;
  	if( n ==1 ){
      	vector<int>f;
      	f.push_back(1);
      	Answer(f);
      	return;
    }
    vector < int > v;
    for( int i = 1; i <= n; i++ ){
        p[i] = i;
        v.push_back(i);
        g[i].push_back(i);
        sz[i] = 1;
    }
    for( int i = 1; i <= n; i++ ){
        int l = 1 , r = (int)v.size() - 1;
        while( l < r ){
            int m = (l + r) / 2;
            vector < int > M(n , 0);
            for( int j = 0; j <= m; j++ ){
                for( auto y : g[get(v[j])] ){
                    M[y - 1] = 1;
                }
            }
            int x = Query(M);
            if( x == m + 1 )l = m + 1;
            else r = m;
        }
        int p = l;
        l = 0 , r = p - 1;
        while( l < r ){
            int m = (l + r) / 2;
            vector < int > M(n , 0);
            assert( m + 1 != p );
            for( int j = m + 1; j <= p; j++ ){
                for( auto y : g[get(v[j])] ){
                    M[y - 1] = 1;
                }
            }
            int x = Query(M);
            if( x == p - m )r = m;
            else l = m + 1;
        }
        vector < int > g;
        for( int j = 0; j < l; j++ ){
            g.push_back(v[j]);
        }
        for( int j = l + 1; j < p; j++ ){
            g.push_back(v[j]);
        }
        for( int j = p + 1; j < (int)v.size(); j++ ){
            g.push_back(v[j]);
        }
        meg( v[l] , v[p] );
        g.push_back(get( v[l] ));
        v = g;
    }
    Answer(g[get(1)]);
}

Subtask #1
19.0 / 19.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 384 KB # of queries: 2272
2 Correct 43 ms 384 KB # of queries: 2285
3 Correct 46 ms 256 KB # of queries: 2406
4 Correct 41 ms 436 KB # of queries: 2398
5 Correct 54 ms 444 KB # of queries: 2391
6 Correct 47 ms 384 KB # of queries: 2432
7 Correct 38 ms 384 KB # of queries: 2402
8 Correct 43 ms 384 KB # of queries: 2272
9 Correct 45 ms 508 KB # of queries: 2374
10 Correct 24 ms 384 KB # of queries: 1380
11 Correct 4 ms 384 KB # of queries: 0
12 Correct 5 ms 384 KB # of queries: 1
13 Correct 5 ms 384 KB # of queries: 3
14 Correct 4 ms 384 KB # of queries: 8
15 Correct 5 ms 384 KB # of queries: 76
16 Correct 7 ms 384 KB # of queries: 177

Subtask #2
81.0 / 81.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 384 KB # of queries: 2272
2 Correct 43 ms 384 KB # of queries: 2285
3 Correct 46 ms 256 KB # of queries: 2406
4 Correct 41 ms 436 KB # of queries: 2398
5 Correct 54 ms 444 KB # of queries: 2391
6 Correct 47 ms 384 KB # of queries: 2432
7 Correct 38 ms 384 KB # of queries: 2402
8 Correct 43 ms 384 KB # of queries: 2272
9 Correct 45 ms 508 KB # of queries: 2374
10 Correct 24 ms 384 KB # of queries: 1380
11 Correct 4 ms 384 KB # of queries: 0
12 Correct 5 ms 384 KB # of queries: 1
13 Correct 5 ms 384 KB # of queries: 3
14 Correct 4 ms 384 KB # of queries: 8
15 Correct 5 ms 384 KB # of queries: 76
16 Correct 7 ms 384 KB # of queries: 177
17 Correct 465 ms 384 KB # of queries: 16594
18 Correct 440 ms 504 KB # of queries: 16530
19 Correct 459 ms 504 KB # of queries: 16548
20 Correct 414 ms 504 KB # of queries: 15562
21 Correct 382 ms 384 KB # of queries: 14484
22 Correct 450 ms 384 KB # of queries: 16654
23 Correct 452 ms 508 KB # of queries: 16599
24 Correct 167 ms 504 KB # of queries: 7560
25 Correct 431 ms 632 KB # of queries: 16286
26 Correct 407 ms 468 KB # of queries: 15129
27 Correct 145 ms 384 KB # of queries: 7515
28 Correct 296 ms 440 KB # of queries: 11010
29 Correct 296 ms 632 KB # of queries: 11248
30 Correct 277 ms 384 KB # of queries: 11010