Submission #451645

#	Time	Username	Problem	Language	Result	Execution time	Memory
451645		ACmachine	Library (JOI18_library)	C++17	19 / 100	346 ms	416 KiB

library

#include <cstdio>
#include <vector>
#include <bits/stdc++.h>
#include "library.h"
using namespace std;
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;

template<typename T> using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
template<typename T, typename U> using ordered_map = tree<T, U, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

typedef long long ll;
typedef long double ld;

typedef pair<int,int> pii;
typedef pair<ll,ll> pll;

typedef vector<int> vi;
typedef vector<ll> vll;

#define FOR(i,j,k,in) for(int i=(j); i < (k);i+=in)
#define FORD(i,j,k,in) for(int i=(j); i >=(k);i-=in)
#define REP(i,b) FOR(i,0,b,1)
#define REPD(i,b) FORD(i,b,0,1)
#define pb push_back
#define mp make_pair
#define ff first
#define ss second
#define all(x) begin(x), end(x)
#define MANY_TESTS int tcase; cin >> tcase; while(tcase--)

const double EPS = 1e-9;
const int MOD = 1e9+7;
const ll INFF = 1e18;
const int INF = 1e9;
const ld PI = acos((ld)-1);
const vi dy = {1, 0, -1, 0, -1, 1, 1, -1};
const vi dx = {0, 1, 0, -1, -1, 1, -1, 1};

void DBG(){cout << "]" << endl;}
template<typename T, typename ...U> void DBG(const T& head, const U... args){ cout << head << "; "; DBG(args...); }
#define dbg(...) cout << "Line(" << __LINE__ << ") -> [" << #__VA_ARGS__ << "]: [", DBG(__VA_ARGS__);
#define chk() cout << "Check at line(" << __LINE__ << ") hit." << endl;

template<class T, unsigned int U>
ostream& operator<<(ostream& out, const array<T, U> &v){out << "[";  REP(i, U) out << v[i] << ", ";  out << "]"; return out;}
template <class T, class U>
ostream& operator<<(ostream& out, const pair<T, U> &par) {out << "[" << par.first << ";" << par.second << "]"; return out;}
template <class T>
ostream& operator<<(ostream& out, const set<T> &cont) { out << "{"; for( const auto &x:cont) out << x << ", "; out << "}"; return out; }
template <class T, class U>
ostream& operator<<(ostream& out, const map<T, U> &cont) {out << "{"; for( const auto &x:cont) out << x << ", "; out << "}"; return out; }
template<class T>
ostream& operator<<(ostream& out, const vector<T> &v){ out << "[";  REP(i, v.size()) out << v[i] << ", ";  out << "]"; return out;}

template<class T>
istream& operator>>(istream& in, vector<T> &v){ for(auto &x : v) in >> x; return in; }

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());


void Solve(int n)
{
	vector<int> m(n);
    vector<vector<int>> components(n);
    REP(i, n){
        components[i].pb(i);
    }
    int found_connections = 0;
    vector<vector<int>> sets;
    vector<int> connection_numbers;
    connection_numbers.pb(n - 1);
    vector<int> tm(n);
    iota(all(tm), 0);
    sets.pb(tm);
    while(found_connections < n - 1){
        if(connection_numbers.back() == 0){
            sets.pop_back();
            connection_numbers.pop_back();
            continue;
        }
        vector<int> nset;
        for(int x : sets.back()){
            if(!components[x].empty())
                nset.pb(x);
        }
        sets.back().swap(nset);
        nset.clear();
        if(sets.back().size() == 2){
            bool found = false;
            vector<int> setc = sets.back();
            REP(j, 2){
                if(found) break;
                REP(k, 2){
                    int u = (j == 0 ? components[setc[0]][0] : components[setc[0]].back());
                    int v = (k == 0 ? components[setc[1]][0] : components[setc[1]].back());
                    fill(all(m), 0);
                    m[u] = m[v] = 1;
                    if((j == 1 && k == 1) || (Query(m) < 2)){
                        found = true;
                        if(j == 0)
                            reverse(all(components[setc[0]]));
                        if(k == 1)
                            reverse(all(components[setc[1]]));
                        for(int x : components[setc[1]])
                            components[setc[0]].pb(x);
                        components[setc[1]].clear();
                        break;
                    }
                }
            }
            found_connections++;
            REP(i, connection_numbers.size())
                connection_numbers[i]--;
            continue;
        }
        int num = max(2, (int)sets.back().size() / 2);
        shuffle(all(sets.back()), rng);
        REP(j, num)
            nset.pb(sets.back()[j]);
        fill(all(m), 0);
        REP(j, nset.size()){
            for(int x : components[nset[j]])
                m[x] = 1;
        }
        int res = Query(m);
        res = nset.size() - res;
        if(res > 0){
            sets.pb(nset);
            connection_numbers.pb(res);
        }
    }
    /*
    REP(i, n - 1){
        vector<int> setc;

        REP(j, components.size()){
            if(components[j].size() > 0)
                setc.pb(j);
        }
        while(setc.size() > 2){
            int num = max(2, (int)setc.size() / 2);
            shuffle(all(setc), rng);
            vector<int> nsetc;
            REP(j, num){
                nsetc.pb(setc[j]);
            }
            fill(all(m), 0);
            REP(j, nsetc.size()){
                for(int x : components[nsetc[j]])
                    m[x] = 1;
            }
            int res = Query(m);
            res = nsetc.size() - res;
            if(res > 0){
                nsetc.swap(setc);
            }
        }
        bool found = false;
        REP(j, 2){
            if(found) break;
            REP(k, 2){
                int u = (j == 0 ? components[setc[0]][0] : components[setc[0]].back());
                int v = (k == 0 ? components[setc[1]][0] : components[setc[1]].back());
                fill(all(m), 0);
                m[u] = m[v] = 1;
                if((j == 1 && k == 1) || (Query(m) < 2)){
                    found = true;
                    if(j == 0)
                        reverse(all(components[setc[0]]));
                    if(k == 1)
                        reverse(all(components[setc[1]]));
                    for(int x : components[setc[1]])
                        components[setc[0]].pb(x);
                    components[setc[1]].clear();
                    break;
                }
            }
        }
    }
     */
    REP(i, n){
        if(components[i].size() > 0){
            for(int& x : components[i])
                x++;
            Answer(components[i]);
            break;
        }
    }
}

Compilation message (stderr)

library.cpp: In function 'void Solve(int)':
library.cpp:22:40: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   22 | #define FOR(i,j,k,in) for(int i=(j); i < (k);i+=in)
      |                                        ^
library.cpp:24:18: note: in expansion of macro 'FOR'
   24 | #define REP(i,b) FOR(i,0,b,1)
      |                  ^~~
library.cpp:114:13: note: in expansion of macro 'REP'
  114 |             REP(i, connection_numbers.size())
      |             ^~~
library.cpp:22:40: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   22 | #define FOR(i,j,k,in) for(int i=(j); i < (k);i+=in)
      |                                        ^
library.cpp:24:18: note: in expansion of macro 'FOR'
   24 | #define REP(i,b) FOR(i,0,b,1)
      |                  ^~~
library.cpp:123:9: note: in expansion of macro 'REP'
  123 |         REP(j, nset.size()){
      |         ^~~

• Subtask 1: 19 / 19
• Subtask 2: 0 / 81