Submission #604232

#	Time	Username	Problem	Language	Result	Execution time	Memory
604232		jeroenodb	Finding Routers (IOI20_routers)	C++14	100 / 100	11 ms	560 KiB

routers

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <tuple>
#include <math.h>
#include <map>
#include "routers.h"

using namespace std;
#define D(a) \
    cout << #a ": " << (a) << ' ';
// Own implemented detector functions
int queries = 0;
map<int,int> answer;
int humandetector(int x) {
    queries++;
    cout << x << endl;
    int k; cin >> k; return k;
}
// int use_detector(int x) {
//     //return humandetector(x);
//     queries++;
//     //cout << x << endl;
//     int ans=-1, dif=1e9;
//     auto iter = answer.upper_bound(x);
//     if(iter!=answer.end()) {
//         dif=abs(x-iter->first);
//         ans=iter->second;
//     }
//     if(iter!=answer.begin()) {
//         iter--;
//         int newdist = abs(x-iter->first);
//         int id = iter->second;
//         if((newdist==dif and id<ans) or newdist<dif) {
//             dif=newdist;
//             ans=id;
//         }
//     }
//     //cout << ans << endl;
//     return ans;

// }

// My solution to the problem
map<int,int> myqueries; // all previous queries are stored to be reused

// Function to find the next router, based on binary search
pair<int,int> routerfind(int prev, int previd, int l,int left ) {
    int rb,i=1,limit = min(l,1+(l+prev)/2);

    // searching for tighter upperbound with previous queries
    auto upb = myqueries.upper_bound(prev);
    while(upb!=myqueries.end()) {
        if(upb->second!=previd) {
            limit = min(limit,upb->first);
            break;
        }
        upb++;
    }

    double x;
    if(left) {
        left= min(left,(limit-prev)/2);
        // x is calculated to be the correct value to begin the doubling search;
        double x = 1-pow(0.6,1/(double)(left+1));
        i=max((int)round((limit-prev)*x),1);
    }
    bool multiple = false;

    // Doubling search
    while(true) {
        if(i+prev>=limit or left==0) {
            rb=limit;
            break;
        }
        int curid = use_detector(prev+i);
        myqueries[prev+i]=curid;
        if(curid!=previd) {
            rb = i+prev;
            break;
        }
        multiple = true;
        i=i*2;
    }
    int lb = prev+1+multiple*(i/2);
    //cout << "Middle must be between " << lb << " and " << rb << endl;
    // Binary search
    while(lb<rb) {
        int mid = (lb+rb)/2;
        int curid = use_detector(mid);
        if(curid==previd) {
            lb=mid+1;
        } else {
            rb=mid;
            myqueries[mid]=curid;
        }
    }
    int newid = -1;
    auto iter = myqueries.find(lb);
    if(iter!=myqueries.end()) newid = iter->second;
    if(newid==-1) {
        newid = use_detector(lb);
    }
    if(newid<previd) {
        return {2*lb-prev,newid};
    } else {
        return {2*(lb-1)-prev,newid};
    }
}
vector<int> find_routers(int l, int n,int q) {
    queries=0;
    myqueries.clear();
    vector<int> ans; ans.resize(n);
    int prev=0,previd=0;
    // iteratively find all routers from left to right.
    for(int i=1;i<n;++i) {
        int pos, id;
        tie(pos,id) = routerfind(prev,previd,l,n-1-i);
        //cout << "found " << id << " at position: " << pos << endl;
        //cout << "queries: " << queries << endl;
        ans[id] = pos;
        prev=pos;previd=id;
    }
    return ans;
}

// random testcase
void generaterandom(int k) {
    for(int i=1;i<k;++i) {
        while(true) {
            int pos = 1+(rand()%49999);
            if(!answer.count(pos*2)) {
                answer[pos*2]=i;
                break;
            }
        }
    }
}

// Equally spaced testcase
void generatespaced(int k,int spacing) {
    for(int i=1;i<k;++i) {
        answer[spacing*i]=i;
    }
}
// int main() {
//     for(int spacing=2;spacing<=100;spacing+=2) for(int k=1000;k<=1000;k++) {
//         answer.clear();
//         answer[0]=0;
        
//         // generaterandom(k);

//         generatespaced(k,spacing);
//         vector<int> ans = find_routers(100000, k,7500);
//         for(int i=0;i<k;++i) {
//             if(answer[ans[i]]!=i) {
//                 cout << "error at " << i << ", " <<ans[i] << endl;
//             }
//         }
//         cout << "spacing is: " << spacing << ", " << queries << " queries used\n";
        
//     }
//     int a; cin >> a;

// }

Compilation message (stderr)

routers.cpp: In function 'std::pair<int, int> routerfind(int, int, int, int)':
routers.cpp:62:12: warning: unused variable 'x' [-Wunused-variable]
   62 |     double x;
      |            ^

• Subtask 1: 16 / 16
• Subtask 2: 21 / 21
• Subtask 3: 23 / 23
• Subtask 4: 40 / 40