Submission #978051

#	Time	Username	Problem	Language	Result	Execution time	Memory
978051		canadavid1	Highway Tolls (IOI18_highway)	C++17	0 / 100	11 ms	1184 KiB

highway

#include "highway.h"
#include <set>
#include <functional>
#include <algorithm>
struct road
{
    int x,y;
    road(int x,int y) : x(x), y(y) {}
};
std::vector<road> roads;


using i64 = long long;
i64 query(std::set<int> U)
{
    std::vector<int> q;q.reserve(roads.size());
    for(auto[x,y] : roads)
    {
        q.push_back(U.count(x)!=U.count(y));
    }
    return ask(q);
}

i64 query(std::function<bool(int)> f)
{
    std::vector<int> q;q.reserve(roads.size());
    for(auto[x,y] : roads)
    {
        q.push_back(f(x)!=f(y));
    }
    return ask(q);
}
bool lt(int x, int y, int bit)
{
    if(x&bit != y&bit) return x&bit < y&bit;
    return x < y;
}
void find_pair(int N, std::vector<int> U, std::vector<int> V, int A, int B) 
{
    for(int i = 0; i < U.size(); i++) roads.emplace_back(U[i],V[i]);
    i64 dist = query(std::set<int>{});

    int xr = 0;
    for(int b = 1; b <= N; b<<=1)
    {
        int r = query([b](int i){return i&b;});
        if(r>dist) xr |= b;
    }
    std::vector<int> n;
    std::sort(n.begin(),n.end(),[xr](int a,int b){return lt(a,b,xr);});
    int l = 0;
    int r = n.size()/2;
    while(l + 1 < r)
    {
        int m = (l+r)/2;
        std::set<int> s;
        for(int i = 0; i < m; i++) s.insert(n[i]);
        auto r = query(s);
        if(r > dist) r = m;
        else l = m;
    }

    answer(n[l],n[l]^xr);
}

Compilation message (stderr)

highway.cpp: In function 'bool lt(int, int, int)':
highway.cpp:35:14: warning: suggest parentheses around comparison in operand of '&' [-Wparentheses]
   35 |     if(x&bit != y&bit) return x&bit < y&bit;
      |          ~~~~^~~~
highway.cpp:35:37: warning: suggest parentheses around comparison in operand of '&' [-Wparentheses]
   35 |     if(x&bit != y&bit) return x&bit < y&bit;
      |                                 ~~~~^~~
highway.cpp: In function 'void find_pair(int, std::vector<int>, std::vector<int>, int, int)':
highway.cpp:40:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   40 |     for(int i = 0; i < U.size(); i++) roads.emplace_back(U[i],V[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