Submission #433302

#	Time	Username	Problem	Language	Result	Execution time	Memory
433302		Tiago_Marques	Finding Routers (IOI20_routers)	C++17	100 / 100	2 ms	304 KiB

routers

#include "routers.h"
#include <bits/stdc++.h>

using namespace std;

typedef long long int ll;

#define REP(i, a, b) for (ll i=a; i<b; i++)
#define pb push_back

std::vector<int> find_routers(int l, int n, int q)
{
    if (n == 2)
    {
        int minimo = 1, maximo = l, x, y;
        while (minimo < maximo - 1)
        {
            int med = (minimo + maximo)/2;
            y = (med + 1)/2;
            while (2*y <= minimo)
                y ++;
            while (2*y-1 >= maximo)
            y --;
            x = use_detector(y);
            if (x == 0)
                minimo = 2*y;
            else
                maximo = 2*y - 1;
        }
        vector<int> ans;
        ans.pb (0);
        if (minimo%2 == 0)
            ans.pb (minimo);
        else
            ans.pb (maximo);
        return ans;
    }
    vector<int> ans(n);
    int minimo[n] = {};
    int maximo[n];
    REP(i, 0, n)
        maximo[i] = l;
    REP(i, 0, n)
    {
        while (minimo[i] < maximo[i])
        {
            int med = (minimo[i] + maximo[i] + 1)/2;
            int x = use_detector(med);
            for (int j=x; j>=0; j--)
            {
                if (maximo[j] <= med - 1)
                    break;
                maximo[j] = med - 1;
            }
            REP(j, x+1, n)
            {
                if (minimo[j] >= med)
                    break;
                minimo[j] = med;
            }
        }
    }
    ans[0] = 0;
    REP(i, 1, n)
        ans[i] = 2*minimo[i] - ans[i-1];
    return ans;
}

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