Submission #823588

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
823588	2023-08-12T19:52:50 Z	sysia	ICC (CEOI16_icc)	C++17	Compilation error	0 ms	0 KB

icc

//Sylwia Sapkowska
#include <bits/stdc++.h>
// #include “icc.h”
#pragma GCC optimize("O3", "unroll-loops")
using namespace std;

void __print(int x) {cerr << x;}
void __print(long long x) {cerr << x;}
void __print(long double x) {cerr << x;}
void __print(char x) {cerr << "'" << x << "'";}
void __print(const char *x) {cerr << '"' << x << '"';}
void __print(const string &x) {cerr << '"' << x << '"';}
void __print(bool x) {cerr << (x ? "true" : "false");}

template<typename T, typename V>
void __print(const pair<T, V> &x) {cerr << '{'; __print(x.first); cerr << ", "; __print(x.second); cerr << '}';}
template<typename T>
void __print(const T &x) {int f = 0; cerr << '{'; for (auto &i: x) cerr << (f++ ? ", " : ""), __print(i); cerr << "}";}
void _print() {cerr << "]\n";}
template <typename T, typename... V>
void _print(T t, V... v) {__print(t); if (sizeof...(v)) cerr << ", "; _print(v...);}
#ifdef LOCAL
#define debug(x...) cerr << "[" << #x << "] = ["; _print(x)
#else
#define debug(x...)
#endif

typedef pair<int, int> T;

mt19937 rng(chrono::steady_clock().now().time_since_epoch().count());
int p(int a, int b){
    return a + rng() % (b-a+1);
}

struct Interactor{
    int n; 
    set<T>s, f;
    vector<T>edges;
    int ptr = 0, cnt = 0;

    void add(){
        if (ptr >= (int)edges.size()) {
            cerr << cnt << "\n";
            cerr << "yay\n";
            return;
        }
        // cerr << "added ";debug(edges[ptr]);
        s.insert(edges[ptr]);
        swap(edges[ptr].first, edges[ptr].second);
        s.insert(edges[ptr]);
        ptr++;
    }

    Interactor(){
        n = 100; 
        // n = 7;   
        debug(n);
        // edges = {{1, 2}, {1, 3}, {4, 2}, {5, 1}, {6, 3}, {7, 3}};
        for (int i = 2; i<=n; i++){
            int par = p(1, i-1);
            edges.emplace_back(i, par);
            debug(i, par);
        }
        add();
    }

    int query(int size_a, int size_b, int a[], int b[]){
        cnt++;
        for (int i = 0; i<size_a; i++){
            for (int j = 0; j<size_b; j++){
                if (s.find({a[i], b[j]}) != s.end()) return 1;
            }
        }
        return 0;
    }

    void setRoad(int a, int b){
        if (s.find({a, b}) == s.end()){
            assert(false);
        } else {
            if (f.find({a, b}) != f.end()){
                assert(false);
            }
            f.insert({a, b});
            f.insert({b, a});
        }
        add();
    }
} I;

struct DSU{
    vector<int>rep, sz;

    DSU(int n){
        rep.resize(n+1);
        iota(rep.begin(), rep.end(), 0);
        sz.assign(n+1, 1);
    }
    
    int f(int a){
        return a == rep[a] ? a : rep[a] = f(rep[a]);
    }

    void u(int a, int b){
        a = f(a); b = f(b);
        assert(a != b);
        if (sz[a] < sz[b]) swap(a, b);
        rep[b] = a;
        sz[a] += sz[b];
    }
};

void run(int n){ //int n as arg
    // int n = I.n;
    vector<vector<int>>tab(n+1);
    DSU dsu(n+1);
    auto create_groups = [&](int cnt){
        for (int rep = 1; rep <= cnt; rep++) tab[rep].clear();
        int ptr = 1;
        vector<int>s(n+1);
        for (int i = 1; i<=n; i++){
            if (dsu.f(i) == i){
                s[i] = ptr++;
            }
        }
        for (int i = 1; i<=n; i++){
            tab[s[dsu.f(i)]].emplace_back(i);
        }
        for (int i = 1; i<=cnt; i++){
            debug(i, tab[i]);
        }
    };
    typedef vector<int> vi;
    auto comp_to_vert = [&](vi &now){
        vector<int>ret;
        for (auto x: now){
            for (auto v: tab[x]){
                ret.emplace_back(v);
            }
        }
        return ret;
    };    
    auto query = [&](vector<int>x, vector<int>y){
        return query((int)x.size(), (int)y.size(), x.data(), y.data());
    };
    vi A, B;
    auto divide = [&](int i){
        int mask = 0;
        for (int p = 0; (1<<p) <= i; p++){
            A.clear(); B.clear();
            for (int rep = 1; rep <= i; rep++){
                if (rep&(1<<p)) A.emplace_back(rep);
                else B.emplace_back(rep);
            }
            if (query(comp_to_vert(A), comp_to_vert(B))) {
                mask += (1<<p);
            }
        }
        return mask;
    };
    auto binsearch = [&](int i, int mask){
        A.clear(); B.clear();
        debug(mask);
        for (int j = 1; j <= i; j++){
            int k = (j^mask);
            if (j < k && k <= n){
                A.emplace_back(j);
                B.emplace_back(k);
            }
        }
        debug(A);
        debug(B);
        vector<int> a = comp_to_vert(A);
        vector<int> b = comp_to_vert(B);
        debug(a, b);
        int ans[2];
        for (int rep = 0; rep < 2; rep++){
            int l = 0, r = (int)a.size()-1;
            ans[rep] = r;
            while (r >= l){
                int mid = (l+r)/2;
                if (query(vi(a.begin(), a.begin()+mid+1), b)) {
                    ans[rep] = a[mid];
                    r = mid-1;
                } else l = mid+1;
            }
            swap(a, b);
        }
        debug(ans[0], ans[1]);
        dsu.u(ans[0], ans[1]);
        setRoad(ans[0], ans[1]);
    };
    for (int i = n; i >= 2; i--){
        create_groups(i);
        binsearch(i, divide(i));
    }
}

// int32_t main(){ run(); }

Compilation message

icc.cpp: In lambda function:
icc.cpp:144:16: error: use of 'query' before deduction of 'auto'
  144 |         return query((int)x.size(), (int)y.size(), x.data(), y.data());
      |                ^~~~~
icc.cpp: In lambda function:
icc.cpp:191:9: error: 'setRoad' was not declared in this scope
  191 |         setRoad(ans[0], ans[1]);
      |         ^~~~~~~