Submission #963692

# Submission time Handle Problem Language Result Execution time Memory
963692 2024-04-15T13:32:37 Z LucaIlie ICC (CEOI16_icc) C++17
18 / 100
263 ms 952 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 );
}

pair<int, int> solve( vector<int> a, vector<int> b ) {
    if ( b.size() == 1 ) {
        if ( a.size() == 1 )
            return { a[0], b[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 solve( a1, b );
        return solve( a2, b );
    }

    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 solve( a, b1 );
    return solve( a, b2 );
}

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


        /*for ( int i = 0; i < a.size(); i++ )
            cout << a[i] << " ";
        cout << "\n";
        for ( int i = 0; i < b.size(); i++ )
            cout << b[i] << " ";
        cout << "\n";
        cout << "\n";*/

        queue<vector<vector<int>>> q;
        q.push( g );
        while ( !q.empty() ) {
            vector<vector<int>> c = q.front();
            q.pop();

            unsigned seed = chrono::system_clock::now().time_since_epoch().count();
            shuffle( c.begin(), c.end(), default_random_engine( seed ) );


            if ( c.size() <= 1 )
                continue;

            /*printf( "%d\n", c.size() );
            for ( auto g: c ) {
                for ( auto v: g )
                    cout << v << " ";
                cout << "\n";
            }
            printf( "\n" );*/
            vector<int> a, b;
            for ( int i = 0; i < c.size() / 2; i++ ) {
                for ( int v: c[i] )
                    a.push_back( v );
            }
            for ( int i = c.size() / 2; i < c.size(); i++ ) {
                for ( int v: c[i] )
                    b.push_back( v );
            }

            if ( qry( a, b ) ) {
                pair<int, int> e = solve( a, b );
                setRoad( e.first, e.second );
                int x = leader[e.first], y = leader[e.second];
                for ( int v: group[y] ) {
                    leader[v] = x;
                    group[x].push_back( v );
                }
                group[y].clear();
                break;
            }

            vector<vector<int>> d, e;
            for ( int i = 0; i < c.size() / 2; i++ )
                d.push_back( c[i] );
            for ( int i = c.size() / 2; i < c.size(); i++ )
                e.push_back( c[i] );

            q.push( d );
            q.push( e );
        }
        while ( !q.empty() )
            q.pop();
    }
}

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 'std::pair<int, int> solve(std::vector<int>, std::vector<int>)':
icc.cpp:25:28: 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:39: 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:36:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   36 |     for ( int i = 0; i < b.size() / 2; i++ )
      |                      ~~^~~~~~~~~~~~~~
icc.cpp:38:35: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   38 |     for ( int i = b.size() / 2; i < b.size(); i++ )
      |                                 ~~^~~~~~~~~~
icc.cpp: In function 'void run(int)':
icc.cpp:88:32: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   88 |             for ( int i = 0; i < c.size() / 2; i++ ) {
      |                              ~~^~~~~~~~~~~~~~
icc.cpp:92:43: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   92 |             for ( int i = c.size() / 2; i < c.size(); i++ ) {
      |                                         ~~^~~~~~~~~~
icc.cpp:110:32: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  110 |             for ( int i = 0; i < c.size() / 2; i++ )
      |                              ~~^~~~~~~~~~~~~~
icc.cpp:112:43: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  112 |             for ( int i = c.size() / 2; i < c.size(); i++ )
      |                                         ~~^~~~~~~~~~
# Verdict Execution time Memory Grader output
1 Correct 5 ms 600 KB Ok! 100 queries used.
2 Correct 5 ms 604 KB Ok! 111 queries used.
# Verdict Execution time Memory Grader output
1 Correct 40 ms 604 KB Ok! 779 queries used.
2 Correct 62 ms 680 KB Ok! 1333 queries used.
3 Correct 65 ms 928 KB Ok! 1332 queries used.
# Verdict Execution time Memory Grader output
1 Incorrect 263 ms 672 KB Too many queries! 4495 out of 2250
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Incorrect 237 ms 952 KB Number of queries more than 4000 out of 2000
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Incorrect 203 ms 692 KB Number of queries more than 3550 out of 1775
2 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Incorrect 205 ms 692 KB Number of queries more than 3250 out of 1625
2 Halted 0 ms 0 KB -