Submission #641851

#	Time	Username	Problem	Language	Result	Execution time	Memory
641851		knon0501	Finding Routers (IOI20_routers)	C++14	77 / 100	2 ms	340 KiB

routers

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

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);
        if(chk[x]==0)chk[x]=i;
        for (; j < x; j++)
        {
            int lef = prv + 1;
            int rig = i - 1;
            if(chk[j])rig=chk[j]-1;
            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:27:31: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   27 |                 int mid = lef + rig >> 1;
      |                           ~~~~^~~~~
routers.cpp:51:27: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   51 |             int mid = lef + rig >> 1;
      |                       ~~~~^~~~~
routers.cpp:63:25: warning: 'k' may be used uninitialized in this function [-Wmaybe-uninitialized]
   63 |         ans.push_back(2 * k - ans[j - 1]);
      |                       ~~^~~
routers.cpp:39:29: warning: 'k' may be used uninitialized in this function [-Wmaybe-uninitialized]
   39 |             ans.push_back(2 * k - ans[j - 1]);
      |                           ~~^~~

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