Submission #1281092

#	Time	Username	Problem	Language	Result	Execution time	Memory
1281092		SSKMF	Finding Routers (IOI20_routers)	C++20	100 / 100	2 ms	376 KiB

routers

#include "routers.h"
#include <bits/stdc++.h>
using namespace std;

inline void Divide (const int stanga , const int dreapta , const int inceput , const int sfarsit , vector <int>& capat)
{
    if (stanga > dreapta)
        { return; }

    if (inceput == sfarsit)
        { capat[stanga] = inceput; return; }

    const int mijloc = (inceput + sfarsit) >> 1;
    const int raspuns = use_detector(mijloc);
    Divide(stanga , raspuns , inceput , mijloc , capat);
    Divide(raspuns + 1 , dreapta , mijloc + 1 , sfarsit , capat);
}

vector <int> find_routers (int lungime , int cantitate , int limita)
{
    if (limita == 20)
    {
        vector <int> rezultat = {0};
        for (int indice = 0 ; indice + 1 < cantitate ; indice++)
        {
            int locatie = rezultat[indice];
            for (int putere = (1 << 16) ; putere ; putere >>= 1) {
                if (locatie + putere <= lungime && use_detector(locatie + putere) == indice)
                    { locatie += putere; }
            }

            rezultat.push_back(2 * locatie - rezultat[indice]);
        }

        return rezultat;
    }
    
    vector <int> rezultat(cantitate);
    Divide(0 , cantitate - 1 , 0 , lungime , rezultat);
    for (int indice = 1 ; indice < cantitate ; indice++)
        { rezultat[indice] += rezultat[indice] - rezultat[indice - 1] - 2; }

    return rezultat;
}

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