Submission #451745

# Submission time Handle Problem Language Result Execution time Memory
451745 2021-08-03T11:37:56 Z ACmachine Library (JOI18_library) C++17
100 / 100
417 ms 3048 KB
#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);
    }
    REP(i, n - 1){
        vector<int> setc;
        REP(j, n){
            if(components[j].size() > 0)
                setc.pb(j);
        }
        int bk = 0;
        REP(j, setc.size()){
            if(components[setc[j]].size() < components[setc[bk]].size())
                bk = j;
        }
        int val = setc[bk];
        setc.erase(setc.begin() + bk);
        bk = val;
        int l = 0;
        int r = setc.size();
        while((r - l) > 1){
            int mid = (l + r) >> 1;
            fill(all(m), 0);
            FOR(j, l, mid, 1){
                for(int x : components[setc[j]])
                    m[x] = 1;
            }
            int f = Query(m);
            for(int x : components[bk])
                m[x] = 1;
            int s = Query(m);
            if(s <= f){
                r = mid;
            }
            else{
                l = mid;
            }
        }
        int sec = setc[l];
        setc.clear();
        setc = {bk, sec};
        // aby som mohol reusnut kod
        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

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:77:9: note: in expansion of macro 'REP'
   77 |         REP(j, setc.size()){
      |         ^~~
# Verdict Execution time Memory Grader output
1 Correct 43 ms 200 KB # of queries: 2656
2 Correct 48 ms 292 KB # of queries: 2654
3 Correct 50 ms 200 KB # of queries: 2799
4 Correct 59 ms 288 KB # of queries: 2801
5 Correct 45 ms 292 KB # of queries: 2798
6 Correct 48 ms 292 KB # of queries: 2801
7 Correct 51 ms 288 KB # of queries: 2806
8 Correct 56 ms 300 KB # of queries: 2660
9 Correct 66 ms 296 KB # of queries: 2790
10 Correct 35 ms 320 KB # of queries: 1645
11 Correct 1 ms 200 KB # of queries: 0
12 Correct 0 ms 200 KB # of queries: 1
13 Correct 1 ms 200 KB # of queries: 4
14 Correct 1 ms 200 KB # of queries: 10
15 Correct 2 ms 200 KB # of queries: 95
16 Correct 4 ms 200 KB # of queries: 217
# Verdict Execution time Memory Grader output
1 Correct 43 ms 200 KB # of queries: 2656
2 Correct 48 ms 292 KB # of queries: 2654
3 Correct 50 ms 200 KB # of queries: 2799
4 Correct 59 ms 288 KB # of queries: 2801
5 Correct 45 ms 292 KB # of queries: 2798
6 Correct 48 ms 292 KB # of queries: 2801
7 Correct 51 ms 288 KB # of queries: 2806
8 Correct 56 ms 300 KB # of queries: 2660
9 Correct 66 ms 296 KB # of queries: 2790
10 Correct 35 ms 320 KB # of queries: 1645
11 Correct 1 ms 200 KB # of queries: 0
12 Correct 0 ms 200 KB # of queries: 1
13 Correct 1 ms 200 KB # of queries: 4
14 Correct 1 ms 200 KB # of queries: 10
15 Correct 2 ms 200 KB # of queries: 95
16 Correct 4 ms 200 KB # of queries: 217
17 Correct 342 ms 360 KB # of queries: 18648
18 Correct 417 ms 368 KB # of queries: 18401
19 Correct 403 ms 348 KB # of queries: 18741
20 Correct 354 ms 340 KB # of queries: 17413
21 Correct 304 ms 352 KB # of queries: 16407
22 Correct 395 ms 364 KB # of queries: 18737
23 Correct 411 ms 344 KB # of queries: 18618
24 Correct 162 ms 328 KB # of queries: 8585
25 Correct 362 ms 360 KB # of queries: 18213
26 Correct 343 ms 476 KB # of queries: 17045
27 Correct 137 ms 324 KB # of queries: 8594
28 Correct 352 ms 2904 KB # of queries: 16956
29 Correct 254 ms 2896 KB # of queries: 16937
30 Correct 297 ms 3048 KB # of queries: 16956