Submission #604118

#	Time	Username	Problem	Language	Result	Execution time	Memory
604118		AlperenT	Highway Tolls (IOI18_highway)	C++17	0 / 100	286 ms	262144 KiB

highway

#include <bits/stdc++.h>
#include "highway.h"

using namespace std;

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

const int N = 9e4, K = 15;

vector<pair<int, int>> graph[N];

vector<int> ones, zeros;

void dfs(int v, int p, bool flag){
    if(flag) ones.push_back(v);
    else zeros.push_back(v);

    for(auto e : graph[v]){
        if(e.first != p){
            dfs(e.first, v, flag ^ 1);
        }
    }
}

void find_pair(int n, vector<int> u, vector<int> v, int a, int b){
    int m = u.size(), s = -1, t = -1;

    for(int i = 0; i < m; i++){
        graph[u[i]].push_back({v[i], i});
        graph[v[i]].push_back({u[i], i});
    }

    vector<int> tmp(m, 0);

    long long dist = ask(tmp);

    dfs(0, -1, 0);

    if(zeros.size() > ones.size()) swap(zeros, ones);

    for(auto x : ones) cout << x << " ";
    cout << "\n";

    for(auto x : zeros) cout << x << " ";
    cout << "\n";

    tmp.assign(m, 0);

    for(auto v : ones){
        for(auto e : graph[v]){
            tmp[e.second] = 1;
        }
    }

    if(((ask(tmp) - dist) / (b - a)) % 2 == 1){
        int l = 0, r = ones.size(), md;

        while(r - l > 1){
            md = l + (r - l) / 2;

            tmp.assign(m, 0);

            for(int i = 0; i < md; i++){
                int v = ones[i];

                for(auto e : graph[v]) tmp[e.second] = 1;
            }

            if(((ask(tmp) - dist) / (b - a)) % 2 == 1) r = md;
            else l = md;
        }

        s = ones[l];

        l = 0, r = zeros.size();

        while(r - l > 1){
            md = l + (r - l) / 2;

            tmp.assign(m, 0);

            for(int i = 0; i < md; i++){
                int v = zeros[i];

                for(auto e : graph[v]) tmp[e.second] = 1;
            }

            if(((ask(tmp) - dist) / (b - a)) % 2 == 1) r = md;
            else l = md;
        }

        t = zeros[l];

        answer(s, t);

        return;
    }
    else{
        for(int it = 0; it < K; it++){
            shuffle(ones.begin(), ones.end(), rng);

            tmp.assign(m, 0);

            for(int i = 0; i <= (ones.size() - 1) / 2; i++){
                int v = ones[i];

                for(auto e : graph[v]) tmp[e.second] = 1;
            }

            if(((ask(tmp) - dist) / (b - a)) % 2 == 1){
                vector<int> seta, setb;

                for(int i = 0; i <= (ones.size() - 1) / 2; i++) seta.push_back(ones[i]);
                for(int i = (ones.size() - 1) / 2 + 1; i < ones.size(); i++) setb.push_back(ones[i]);

                int l = 0, r = seta.size(), md;

                while(r - l > 1){
                    md = l + (r - l) / 2;

                    tmp.assign(m, 0);

                    for(int i = 0; i < md; i++){
                        int v = seta[i];

                        for(auto e : graph[v]) tmp[e.second] = 1;
                    }

                    if(((ask(tmp) - dist) / (b - a)) % 2 == 1) r = md;
                    else l = md;
                }

                s = seta[l];

                l = 0, r = setb.size();

                while(r - l > 1){
                    md = l + (r - l) / 2;

                    tmp.assign(m, 0);

                    for(int i = 0; i < md; i++){
                        int v = setb[i];

                        for(auto e : graph[v]) tmp[e.second] = 1;
                    }

                    if(((ask(tmp) - dist) / (b - a)) % 2 == 1) r = md;
                    else l = md;
                }

                t = setb[l];

                answer(s, t);

                return;
            }
        }

        for(int it = 0; it < K; it++){
            shuffle(zeros.begin(), zeros.end(), rng);

            tmp.assign(m, 0);

            for(int i = 0; i <= (zeros.size() - 1) / 2; i++){
                int v = zeros[i];

                for(auto e : graph[v]) tmp[e.second] = 1;
            }

            if(((ask(tmp) - dist) / (b - a)) % 2 == 1){
                vector<int> seta, setb;

                for(int i = 0; i <= (zeros.size() - 1) / 2; i++) seta.push_back(zeros[i]);
                for(int i = (zeros.size() - 1) / 2 + 1; i < zeros.size(); i++) setb.push_back(zeros[i]);

                int l = 0, r = seta.size(), md;

                while(r - l > 1){
                    md = l + (r - l) / 2;

                    tmp.assign(m, 0);

                    for(int i = 0; i < md; i++){
                        int v = seta[i];

                        for(auto e : graph[v]) tmp[e.second] = 1;
                    }

                    if(((ask(tmp) - dist) / (b - a)) % 2 == 1) r = md;
                    else l = md;
                }

                s = seta[l];

                l = 0, r = setb.size();

                while(r - l > 1){
                    md = l + (r - l) / 2;

                    tmp.assign(m, 0);

                    for(int i = 0; i < md; i++){
                        int v = setb[i];

                        for(auto e : graph[v]) tmp[e.second] = 1;
                    }

                    if(((ask(tmp) - dist) / (b - a)) % 2 == 1) r = md;
                    else l = md;
                }

                t = setb[l];

                answer(s, t);

                return;
            }
        }
    }

    assert(false);
}

Compilation message (stderr)

highway.cpp: In function 'void find_pair(int, std::vector<int>, std::vector<int>, int, int)':
highway.cpp:104:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  104 |             for(int i = 0; i <= (ones.size() - 1) / 2; i++){
      |                            ~~^~~~~~~~~~~~~~~~~~~~~~~~
highway.cpp:113:34: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  113 |                 for(int i = 0; i <= (ones.size() - 1) / 2; i++) seta.push_back(ones[i]);
      |                                ~~^~~~~~~~~~~~~~~~~~~~~~~~
highway.cpp:114:58: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  114 |                 for(int i = (ones.size() - 1) / 2 + 1; i < ones.size(); i++) setb.push_back(ones[i]);
      |                                                        ~~^~~~~~~~~~~~~
highway.cpp:165:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  165 |             for(int i = 0; i <= (zeros.size() - 1) / 2; i++){
      |                            ~~^~~~~~~~~~~~~~~~~~~~~~~~~
highway.cpp:174:34: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  174 |                 for(int i = 0; i <= (zeros.size() - 1) / 2; i++) seta.push_back(zeros[i]);
      |                                ~~^~~~~~~~~~~~~~~~~~~~~~~~~
highway.cpp:175:59: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  175 |                 for(int i = (zeros.size() - 1) / 2 + 1; i < zeros.size(); i++) setb.push_back(zeros[i]);
      |                                                         ~~^~~~~~~~~~~~~~

• Subtask 1: 0 / 5
• Subtask 2: 0 / 7
• Subtask 3: 0 / 6
• Subtask 4: 0 / 33
• Subtask 5: 0 / 18
• Subtask 6: 0 / 31