oj.uz

Submission #230311

# Submission time Handle Problem Language Result Execution time Memory
230311 2020-05-09T14:06:34 Z muhammad_hokimiyon Library (JOI18_library) C++14
0 / 100
 465 ms 648 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;
    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

# Verdict Execution time Memory Grader output
1 Correct 42 ms 384 KB # of queries: 2272
2 Correct 38 ms 384 KB # of queries: 2285
3 Correct 42 ms 384 KB # of queries: 2406
4 Correct 41 ms 384 KB # of queries: 2398
5 Correct 44 ms 384 KB # of queries: 2391
6 Correct 32 ms 404 KB # of queries: 2432
7 Correct 41 ms 384 KB # of queries: 2402
8 Correct 46 ms 384 KB # of queries: 2272
9 Correct 44 ms 384 KB # of queries: 2374
10 Correct 26 ms 384 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 5 ms 384 KB # of queries: 1
13 Correct 4 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
0 / 81.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 384 KB # of queries: 2272
2 Correct 38 ms 384 KB # of queries: 2285
3 Correct 42 ms 384 KB # of queries: 2406
4 Correct 41 ms 384 KB # of queries: 2398
5 Correct 44 ms 384 KB # of queries: 2391
6 Correct 32 ms 404 KB # of queries: 2432
7 Correct 41 ms 384 KB # of queries: 2402
8 Correct 46 ms 384 KB # of queries: 2272
9 Correct 44 ms 384 KB # of queries: 2374
10 Correct 26 ms 384 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 5 ms 384 KB # of queries: 1
13 Correct 4 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 459 ms 440 KB # of queries: 16594
18 Correct 458 ms 384 KB # of queries: 16530
19 Correct 465 ms 648 KB # of queries: 16548
20 Correct 411 ms 504 KB # of queries: 15562
21 Correct 380 ms 632 KB # of queries: 14484
22 Correct 465 ms 504 KB # of queries: 16654
23 Correct 442 ms 504 KB # of queries: 16599
24 Correct 159 ms 504 KB # of queries: 7560
25 Correct 452 ms 384 KB # of queries: 16286
26 Correct 395 ms 476 KB # of queries: 15129
27 Correct 156 ms 416 KB # of queries: 7515
28 Correct 290 ms 436 KB # of queries: 11010
29 Correct 300 ms 504 KB # of queries: 11248
30 Correct 314 ms 384 KB # of queries: 11010