oj.uz

Submission #978051

# Submission time Handle Problem Language Result Execution time Memory
978051 2024-05-08T17:41:49 Z canadavid1 Highway Tolls (IOI18_highway) C++17
0 / 100
 11 ms 1184 KB 
#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

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.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 428 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #2
0 / 7.0

# Verdict Execution time Memory Grader output
1 Runtime error 2 ms 452 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #3
0 / 6.0

# Verdict Execution time Memory Grader output
1 Runtime error 9 ms 1164 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #4
0 / 33.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 456 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #5
0 / 18.0

# Verdict Execution time Memory Grader output
1 Runtime error 11 ms 1084 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #6
0 / 31.0

# Verdict Execution time Memory Grader output
1 Runtime error 10 ms 1184 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -