oj.uz

답안 #230308

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

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;
    }
    for( auto x : g[get(1)] ){
        cout << x << " ";
    }
}

Subtask #1
0 / 19.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 39 ms 404 KB DO NOT WRITE ANYTHING TO STANDARD OUTPUT
2 Incorrect 43 ms 384 KB DO NOT WRITE ANYTHING TO STANDARD OUTPUT
3 Incorrect 51 ms 412 KB DO NOT WRITE ANYTHING TO STANDARD OUTPUT
4 Incorrect 51 ms 384 KB DO NOT WRITE ANYTHING TO STANDARD OUTPUT
5 Incorrect 45 ms 384 KB DO NOT WRITE ANYTHING TO STANDARD OUTPUT
6 Incorrect 43 ms 384 KB DO NOT WRITE ANYTHING TO STANDARD OUTPUT
7 Incorrect 42 ms 384 KB DO NOT WRITE ANYTHING TO STANDARD OUTPUT
8 Incorrect 46 ms 504 KB DO NOT WRITE ANYTHING TO STANDARD OUTPUT
9 Incorrect 48 ms 384 KB DO NOT WRITE ANYTHING TO STANDARD OUTPUT
10 Incorrect 19 ms 408 KB DO NOT WRITE ANYTHING TO STANDARD OUTPUT
11 Runtime error 5 ms 512 KB Execution killed with signal 11 (could be triggered by violating memory limits)
12 Incorrect 4 ms 384 KB DO NOT WRITE ANYTHING TO STANDARD OUTPUT
13 Incorrect 5 ms 384 KB DO NOT WRITE ANYTHING TO STANDARD OUTPUT
14 Incorrect 5 ms 384 KB DO NOT WRITE ANYTHING TO STANDARD OUTPUT
15 Incorrect 6 ms 384 KB DO NOT WRITE ANYTHING TO STANDARD OUTPUT
16 Incorrect 7 ms 384 KB DO NOT WRITE ANYTHING TO STANDARD OUTPUT

Subtask #2
0 / 81.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 39 ms 404 KB DO NOT WRITE ANYTHING TO STANDARD OUTPUT
2 Incorrect 43 ms 384 KB DO NOT WRITE ANYTHING TO STANDARD OUTPUT
3 Incorrect 51 ms 412 KB DO NOT WRITE ANYTHING TO STANDARD OUTPUT
4 Incorrect 51 ms 384 KB DO NOT WRITE ANYTHING TO STANDARD OUTPUT
5 Incorrect 45 ms 384 KB DO NOT WRITE ANYTHING TO STANDARD OUTPUT
6 Incorrect 43 ms 384 KB DO NOT WRITE ANYTHING TO STANDARD OUTPUT
7 Incorrect 42 ms 384 KB DO NOT WRITE ANYTHING TO STANDARD OUTPUT
8 Incorrect 46 ms 504 KB DO NOT WRITE ANYTHING TO STANDARD OUTPUT
9 Incorrect 48 ms 384 KB DO NOT WRITE ANYTHING TO STANDARD OUTPUT
10 Incorrect 19 ms 408 KB DO NOT WRITE ANYTHING TO STANDARD OUTPUT
11 Runtime error 5 ms 512 KB Execution killed with signal 11 (could be triggered by violating memory limits)
12 Incorrect 4 ms 384 KB DO NOT WRITE ANYTHING TO STANDARD OUTPUT
13 Incorrect 5 ms 384 KB DO NOT WRITE ANYTHING TO STANDARD OUTPUT
14 Incorrect 5 ms 384 KB DO NOT WRITE ANYTHING TO STANDARD OUTPUT
15 Incorrect 6 ms 384 KB DO NOT WRITE ANYTHING TO STANDARD OUTPUT
16 Incorrect 7 ms 384 KB DO NOT WRITE ANYTHING TO STANDARD OUTPUT
17 Incorrect 500 ms 472 KB DO NOT WRITE ANYTHING TO STANDARD OUTPUT
18 Incorrect 511 ms 632 KB DO NOT WRITE ANYTHING TO STANDARD OUTPUT
19 Incorrect 468 ms 576 KB DO NOT WRITE ANYTHING TO STANDARD OUTPUT
20 Incorrect 481 ms 504 KB DO NOT WRITE ANYTHING TO STANDARD OUTPUT
21 Incorrect 400 ms 384 KB DO NOT WRITE ANYTHING TO STANDARD OUTPUT
22 Incorrect 471 ms 632 KB DO NOT WRITE ANYTHING TO STANDARD OUTPUT
23 Incorrect 515 ms 504 KB DO NOT WRITE ANYTHING TO STANDARD OUTPUT
24 Incorrect 166 ms 384 KB DO NOT WRITE ANYTHING TO STANDARD OUTPUT
25 Incorrect 449 ms 384 KB DO NOT WRITE ANYTHING TO STANDARD OUTPUT
26 Incorrect 417 ms 504 KB DO NOT WRITE ANYTHING TO STANDARD OUTPUT
27 Incorrect 159 ms 508 KB DO NOT WRITE ANYTHING TO STANDARD OUTPUT
28 Incorrect 310 ms 504 KB DO NOT WRITE ANYTHING TO STANDARD OUTPUT
29 Incorrect 322 ms 480 KB DO NOT WRITE ANYTHING TO STANDARD OUTPUT
30 Incorrect 334 ms 384 KB DO NOT WRITE ANYTHING TO STANDARD OUTPUT