답안 #963983

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
963983 2024-04-16T06:58:48 Z LucaIlie CEOI16_icc (CEOI16_icc) C++17
100 / 100
100 ms 856 KB
#include "icc.h"
#include <bits/stdc++.h>

using namespace std;

const int MAX_N = 100;
int leader[MAX_N + 1];
vector<int> group[MAX_N + 1];

bool qry( vector<int> a, vector<int> b ) {
    int aa[a.size()], bb[b.size()];
    for ( int i = 0; i < a.size(); i++ )
        aa[i] = a[i];
    for ( int i = 0; i < b.size(); i++ )
        bb[i] = b[i];
    return query( a.size(), b.size(), aa, bb );
}

int bit;
int solveA( vector<int> a, vector<int> b ) {
    if ( a.size() == 1 )
        return a[0];

    vector<int> a1, a2;
    for ( int i = 0; i < a.size() / 2; i++ )
        a1.push_back( a[i] );
    for ( int i = a.size() / 2; i < a.size(); i++ )
        a2.push_back( a[i] );

    if ( qry( a1, b ) )
        return solveA( a1, b );
    return solveA( a2, b );
}
int solveB( vector<int> a, vector<int> b ) {
    if ( b.size() == 1 )
        return b[0];

    vector<int> b1, b2;
    for ( int i = 0; i < b.size() / 2; i++ )
        b1.push_back( b[i] );
    for ( int i = b.size() / 2; i < b.size(); i++ )
        b2.push_back( b[i] );

    if ( qry( a, b1 ) )
        return solveB( a, b1 );
    return solveB( a, b2 );
}

void run( int n ) {
    for ( int v = 1; v <= n; v++ ) {
        leader[v] = v;
        group[v].push_back( v );
    }
    for ( int pas = 0; pas < n - 1; pas++ ) {
        vector<vector<int>> g;
        for ( int v = 1; v <= n; v++ ) {
            if ( leader[v] == v )
                g.push_back( group[v] );
        }


        int p = 0;
        while ( 1 ) {
            vector<int> s[2];
            for ( int i = 0; i < g.size(); i++ ) {
                int b = (i >> p) & 1;
                for ( int v: g[i] )
                    s[b].push_back( v );
            }

            if ( qry( s[0], s[1] ) ) {
                int first = solveA( s[0], s[1] );

                int j = 0;
                for ( int i = 0; i < g.size(); i++ ) {
                    for ( int v: g[i] ) {
                        if ( v == first )
                            j = i;
                    }
                }
                s[0].clear();
                s[1].clear();
                s[0].push_back( first );
                for ( int i = 0; i < g.size(); i++ ) {
                    bool ok = true;
                    for ( int b = 0; b < p; b++ ) {
                        if (((j >> b) & 1) != ((i >> b) & 1))
                            ok = false;
                    }
                    if ( ((j >> p) & 1) == ((i >> p) & 1) )
                        ok = false;

                    if ( ok ) {
                        for ( int v: g[i] )
                            s[1].push_back( v );
                    }
                }
                int second = solveB( s[0], s[1] );

                setRoad( first, second );
                int x = leader[first], y = leader[second];
                for ( int v: group[y] ) {
                    leader[v] = x;
                    group[x].push_back( v );
                }
                group[y].clear();
                break;
            }

            p++;
        }
    }
}

Compilation message

icc.cpp: In function 'bool qry(std::vector<int>, std::vector<int>)':
icc.cpp:12:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   12 |     for ( int i = 0; i < a.size(); i++ )
      |                      ~~^~~~~~~~~~
icc.cpp:14:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   14 |     for ( int i = 0; i < b.size(); i++ )
      |                      ~~^~~~~~~~~~
icc.cpp: In function 'int solveA(std::vector<int>, std::vector<int>)':
icc.cpp:25:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   25 |     for ( int i = 0; i < a.size() / 2; i++ )
      |                      ~~^~~~~~~~~~~~~~
icc.cpp:27:35: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   27 |     for ( int i = a.size() / 2; i < a.size(); i++ )
      |                                 ~~^~~~~~~~~~
icc.cpp: In function 'int solveB(std::vector<int>, std::vector<int>)':
icc.cpp:39:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   39 |     for ( int i = 0; i < b.size() / 2; i++ )
      |                      ~~^~~~~~~~~~~~~~
icc.cpp:41:35: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   41 |     for ( int i = b.size() / 2; i < b.size(); i++ )
      |                                 ~~^~~~~~~~~~
icc.cpp: In function 'void run(int)':
icc.cpp:65:32: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   65 |             for ( int i = 0; i < g.size(); i++ ) {
      |                              ~~^~~~~~~~~~
icc.cpp:75:36: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   75 |                 for ( int i = 0; i < g.size(); i++ ) {
      |                                  ~~^~~~~~~~~~
icc.cpp:84:36: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   84 |                 for ( int i = 0; i < g.size(); i++ ) {
      |                                  ~~^~~~~~~~~~
# 결과 실행 시간 메모리 Grader output
1 Correct 4 ms 600 KB Ok! 96 queries used.
2 Correct 4 ms 604 KB Ok! 100 queries used.
# 결과 실행 시간 메모리 Grader output
1 Correct 22 ms 604 KB Ok! 520 queries used.
2 Correct 34 ms 600 KB Ok! 543 queries used.
3 Correct 23 ms 600 KB Ok! 543 queries used.
# 결과 실행 시간 메모리 Grader output
1 Correct 73 ms 648 KB Ok! 1283 queries used.
2 Correct 76 ms 640 KB Ok! 1293 queries used.
3 Correct 64 ms 652 KB Ok! 1223 queries used.
4 Correct 73 ms 644 KB Ok! 1310 queries used.
# 결과 실행 시간 메모리 Grader output
1 Correct 71 ms 604 KB Ok! 1292 queries used.
2 Correct 72 ms 856 KB Ok! 1308 queries used.
3 Correct 75 ms 640 KB Ok! 1290 queries used.
4 Correct 67 ms 636 KB Ok! 1252 queries used.
# 결과 실행 시간 메모리 Grader output
1 Correct 100 ms 856 KB Ok! 1323 queries used.
2 Correct 71 ms 648 KB Ok! 1316 queries used.
3 Correct 72 ms 636 KB Ok! 1311 queries used.
4 Correct 68 ms 636 KB Ok! 1295 queries used.
5 Correct 78 ms 656 KB Ok! 1328 queries used.
6 Correct 86 ms 636 KB Ok! 1291 queries used.
# 결과 실행 시간 메모리 Grader output
1 Correct 83 ms 644 KB Ok! 1312 queries used.
2 Correct 85 ms 652 KB Ok! 1300 queries used.