Submission #641845

#	Time	Username	Problem	Language	Result	Execution time	Memory
641845		knon0501	Finding Routers (IOI20_routers)	C++14	53.26 / 100	1 ms	468 KiB

routers

#include "routers.h"
#include <bits/stdc++.h>;
using namespace std;
const int B=150;
int c[1005];
int b[200005];

std::vector<int> find_routers(int l, int n, int q) {
    vector<int> ans={0};
   // cout<<l<<" "<<n<<" "<<q<<endl;
    int j=1;
    int prv=0;
    for(int i=B ; i<=l ; i+=B){
        int x=use_detector(i);
        for( ; j<x ; j++){
            int lef=prv+1;
            int rig=i-1;
            if(rig-lef>5*B){
                rig-=B;
                lef+=B;
            }
            int k;
            while(rig>=lef){
                int mid=lef+rig>>1;
                int y=use_detector(mid);
                if(y<j){
                    k=mid;
                    lef=mid+1;
                }
                else{
                    rig=mid-1;
                }
            }
            ans.push_back(2*k-ans[j-1]);
            prv=ans[j];
        }
    }
    for (; j <n; j++)
    {
        int lef = prv + 1;
        int rig = l;
  
        int k;
        while (rig >= lef)
        {
            int mid = lef + rig >> 1;
            int y = use_detector(mid);
            if (y < j)
            {
                k = mid;
                lef = mid + 1;
            }
            else
            {
                rig = mid - 1;
            }
        }
        ans.push_back(2 * k - ans[j - 1]);
        prv = ans[j];
    }
    return ans;
}

Compilation message (stderr)

routers.cpp:2:25: warning: extra tokens at end of #include directive
    2 | #include <bits/stdc++.h>;
      |                         ^
routers.cpp: In function 'std::vector<int> find_routers(int, int, int)':
routers.cpp:24:28: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   24 |                 int mid=lef+rig>>1;
      |                         ~~~^~~~
routers.cpp:46:27: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   46 |             int mid = lef + rig >> 1;
      |                       ~~~~^~~~~
routers.cpp:58:25: warning: 'k' may be used uninitialized in this function [-Wmaybe-uninitialized]
   58 |         ans.push_back(2 * k - ans[j - 1]);
      |                       ~~^~~
routers.cpp:34:28: warning: 'k' may be used uninitialized in this function [-Wmaybe-uninitialized]
   34 |             ans.push_back(2*k-ans[j-1]);
      |                           ~^~

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