Submission #230368

#	Time	Username	Problem	Language	Result	Execution time	Memory
230368		muhammad_hokimiyon	Library (JOI18_library)	C++14	100 / 100	465 ms	632 KiB

library

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