Submission #280427

#	Time	Username	Problem	Language	Result	Execution time	Memory
280427		salma	Highway Tolls (IOI18_highway)	C++14	0 / 100	18 ms	760 KiB

highway

#include "highway.h"
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;


vector<int>ans;
vector<int>w;
ll toll , dp;

void solve(int lo , int hi){

    if(lo == hi){
        w[lo] = 1;
        if(ask(w) > toll)
            ans.push_back(lo);
        w[lo] = 0;
        return;
    }

    int md = (lo+hi)/2;
    int ok = 0;

    for(int i = lo ; i<=md ; i++)
        w[i] = 1;
    if(ask(w) > toll)
        ok = 1;
     for(int i = lo ; i<=md ; i++)
        w[i] = 0;
    if(ok) solve(lo , md);
    ok = 0;

     for(int i = md+1 ; i<=hi ; i++)
        w[i] = 1;
    if(ask(w) > toll)
        ok = 1;
     for(int i = md+1 ; i<=hi ; i++)
        w[i] = 0;

    if(ok) solve(md+1 , hi);

    return ;
}


void find_pair(int N, vector<int> U, vector<int> V, int A, int B) {
    int M = U.size();

    for (int i = 0; i < M; ++i) {
       w.push_back(0);
    }
    toll = ask(w);
    dp = toll / A;

    solve(0,M-1);

    map<int,int>m;
    for(int i=0;i<dp;i++){
        m[U[ans[i]]]++;
        m[V[ans[i]]]++;
    }
    map<int,int>::iterator it = m.begin();

    int S=-1,T=-1;
    for(; it!=m.end();it++){
        if(it->second == 1){
            if(S == -1)S=it->first;
            else{
                T = it->first;
                break;
            }
        }
    }
  answer(S, T);
}

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