oj.uz

답안 #230310

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
230310 2020-05-09T14:05:20 Z muhammad_hokimiyon 도서관 (JOI18_library) C++14
0 / 100
 473 ms 584 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);
}

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;
    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
0 / 19.0

# 결과 실행 시간 메모리 Grader output
1 Correct 40 ms 384 KB # of queries: 2272
2 Correct 44 ms 384 KB # of queries: 2285
3 Correct 47 ms 400 KB # of queries: 2406
4 Correct 43 ms 384 KB # of queries: 2398
5 Correct 41 ms 384 KB # of queries: 2391
6 Correct 42 ms 384 KB # of queries: 2432
7 Correct 55 ms 384 KB # of queries: 2402
8 Correct 49 ms 384 KB # of queries: 2272
9 Correct 45 ms 384 KB # of queries: 2374
10 Correct 24 ms 400 KB # of queries: 1380
11 Runtime error 5 ms 512 KB Execution killed with signal 11 (could be triggered by violating memory limits)
12 Correct 4 ms 384 KB # of queries: 1
13 Correct 4 ms 384 KB # of queries: 3
14 Correct 5 ms 384 KB # of queries: 8
15 Correct 6 ms 384 KB # of queries: 76
16 Correct 7 ms 384 KB # of queries: 177

Subtask #2
0 / 81.0

# 결과 실행 시간 메모리 Grader output
1 Correct 40 ms 384 KB # of queries: 2272
2 Correct 44 ms 384 KB # of queries: 2285
3 Correct 47 ms 400 KB # of queries: 2406
4 Correct 43 ms 384 KB # of queries: 2398
5 Correct 41 ms 384 KB # of queries: 2391
6 Correct 42 ms 384 KB # of queries: 2432
7 Correct 55 ms 384 KB # of queries: 2402
8 Correct 49 ms 384 KB # of queries: 2272
9 Correct 45 ms 384 KB # of queries: 2374
10 Correct 24 ms 400 KB # of queries: 1380
11 Runtime error 5 ms 512 KB Execution killed with signal 11 (could be triggered by violating memory limits)
12 Correct 4 ms 384 KB # of queries: 1
13 Correct 4 ms 384 KB # of queries: 3
14 Correct 5 ms 384 KB # of queries: 8
15 Correct 6 ms 384 KB # of queries: 76
16 Correct 7 ms 384 KB # of queries: 177
17 Correct 442 ms 476 KB # of queries: 16594
18 Correct 463 ms 584 KB # of queries: 16530
19 Correct 471 ms 384 KB # of queries: 16548
20 Correct 421 ms 504 KB # of queries: 15562
21 Correct 394 ms 568 KB # of queries: 14484
22 Correct 457 ms 504 KB # of queries: 16654
23 Correct 470 ms 444 KB # of queries: 16599
24 Correct 158 ms 384 KB # of queries: 7560
25 Correct 473 ms 440 KB # of queries: 16286
26 Correct 417 ms 476 KB # of queries: 15129
27 Correct 155 ms 384 KB # of queries: 7515
28 Correct 288 ms 384 KB # of queries: 11010
29 Correct 304 ms 384 KB # of queries: 11248
30 Correct 295 ms 504 KB # of queries: 11010