Submission #641818

#	Time	Username	Problem	Language	Result	Execution time	Memory
641818		knon0501	Finding Routers (IOI20_routers)	C++14	74.48 / 100	2 ms	596 KiB

routers

#include "routers.h"
#include <bits/stdc++.h>;
using namespace std;
const int B=255;
int c[1005];
int b[200005];
int memo[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;
            int k;
            while(rig>=lef){
                int mid=lef+rig>>1;
              	int y;
              	if(memo[mid]){
                 	y=memo[mid];
                }
              	else
               	 	y=use_detector(mid);
              	memo[mid]=y;
                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;
              	if(memo[mid]){
                 	y=memo[mid];
                }
              	else
               	 	y=use_detector(mid);
              	memo[mid]=y;
            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:21:28: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   21 |                 int mid=lef+rig>>1;
      |                         ~~~^~~~
routers.cpp:48:27: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   48 |             int mid = lef + rig >> 1;
      |                       ~~~~^~~~~
routers.cpp:66:25: warning: 'k' may be used uninitialized in this function [-Wmaybe-uninitialized]
   66 |         ans.push_back(2 * k - ans[j - 1]);
      |                       ~~^~~
routers.cpp:37:28: warning: 'k' may be used uninitialized in this function [-Wmaybe-uninitialized]
   37 |             ans.push_back(2*k-ans[j-1]);
      |                           ~^~

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