#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
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;
| ^
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Correct |
6 ms |
212 KB |
Output is correct |
3 |
Correct |
6 ms |
300 KB |
Output is correct |
4 |
Correct |
0 ms |
212 KB |
Output is correct |
5 |
Correct |
1 ms |
212 KB |
Output is correct |
6 |
Correct |
0 ms |
212 KB |
Output is correct |
7 |
Correct |
1 ms |
304 KB |
Output is correct |
8 |
Correct |
5 ms |
304 KB |
Output is correct |
9 |
Correct |
3 ms |
300 KB |
Output is correct |
10 |
Correct |
1 ms |
212 KB |
Output is correct |
11 |
Correct |
1 ms |
296 KB |
Output is correct |
12 |
Correct |
2 ms |
212 KB |
Output is correct |
13 |
Correct |
1 ms |
212 KB |
Output is correct |
14 |
Correct |
1 ms |
212 KB |
Output is correct |
15 |
Correct |
0 ms |
212 KB |
Output is correct |
16 |
Correct |
0 ms |
212 KB |
Output is correct |
17 |
Correct |
0 ms |
300 KB |
Output is correct |
18 |
Correct |
0 ms |
212 KB |
Output is correct |
19 |
Correct |
1 ms |
212 KB |
Output is correct |
20 |
Correct |
6 ms |
296 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
304 KB |
Output is correct |
2 |
Correct |
1 ms |
212 KB |
Output is correct |
3 |
Correct |
1 ms |
212 KB |
Output is correct |
4 |
Correct |
1 ms |
212 KB |
Output is correct |
5 |
Correct |
1 ms |
212 KB |
Output is correct |
6 |
Correct |
1 ms |
212 KB |
Output is correct |
7 |
Correct |
1 ms |
212 KB |
Output is correct |
8 |
Correct |
1 ms |
212 KB |
Output is correct |
9 |
Correct |
1 ms |
212 KB |
Output is correct |
10 |
Correct |
1 ms |
212 KB |
Output is correct |
11 |
Correct |
1 ms |
212 KB |
Output is correct |
12 |
Correct |
1 ms |
300 KB |
Output is correct |
13 |
Correct |
1 ms |
212 KB |
Output is correct |
14 |
Correct |
1 ms |
296 KB |
Output is correct |
15 |
Correct |
1 ms |
212 KB |
Output is correct |
16 |
Correct |
1 ms |
300 KB |
Output is correct |
17 |
Correct |
1 ms |
212 KB |
Output is correct |
18 |
Correct |
1 ms |
212 KB |
Output is correct |
19 |
Correct |
1 ms |
212 KB |
Output is correct |
20 |
Correct |
1 ms |
212 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
212 KB |
Output is correct |
2 |
Correct |
1 ms |
300 KB |
Output is correct |
3 |
Correct |
1 ms |
212 KB |
Output is correct |
4 |
Correct |
1 ms |
212 KB |
Output is correct |
5 |
Correct |
1 ms |
212 KB |
Output is correct |
6 |
Correct |
1 ms |
212 KB |
Output is correct |
7 |
Correct |
1 ms |
212 KB |
Output is correct |
8 |
Correct |
1 ms |
212 KB |
Output is correct |
9 |
Correct |
1 ms |
212 KB |
Output is correct |
10 |
Correct |
0 ms |
212 KB |
Output is correct |
11 |
Correct |
1 ms |
212 KB |
Output is correct |
12 |
Correct |
1 ms |
212 KB |
Output is correct |
13 |
Correct |
1 ms |
212 KB |
Output is correct |
14 |
Correct |
1 ms |
212 KB |
Output is correct |
15 |
Correct |
0 ms |
212 KB |
Output is correct |
16 |
Correct |
0 ms |
212 KB |
Output is correct |
17 |
Correct |
1 ms |
212 KB |
Output is correct |
18 |
Correct |
0 ms |
212 KB |
Output is correct |
19 |
Correct |
0 ms |
212 KB |
Output is correct |
20 |
Correct |
0 ms |
300 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
8 ms |
468 KB |
Output is correct |
2 |
Correct |
2 ms |
468 KB |
Output is correct |
3 |
Correct |
2 ms |
468 KB |
Output is correct |
4 |
Correct |
2 ms |
468 KB |
Output is correct |
5 |
Correct |
2 ms |
468 KB |
Output is correct |
6 |
Correct |
3 ms |
468 KB |
Output is correct |
7 |
Correct |
2 ms |
468 KB |
Output is correct |
8 |
Correct |
2 ms |
468 KB |
Output is correct |
9 |
Correct |
2 ms |
468 KB |
Output is correct |
10 |
Correct |
2 ms |
468 KB |
Output is correct |
11 |
Correct |
1 ms |
340 KB |
Output is correct |
12 |
Correct |
2 ms |
468 KB |
Output is correct |
13 |
Correct |
11 ms |
340 KB |
Output is correct |
14 |
Correct |
2 ms |
432 KB |
Output is correct |
15 |
Correct |
2 ms |
468 KB |
Output is correct |
16 |
Correct |
2 ms |
468 KB |
Output is correct |
17 |
Correct |
2 ms |
468 KB |
Output is correct |
18 |
Correct |
2 ms |
560 KB |
Output is correct |
19 |
Correct |
2 ms |
468 KB |
Output is correct |
20 |
Correct |
2 ms |
468 KB |
Output is correct |
21 |
Correct |
2 ms |
468 KB |
Output is correct |