Submission #1203017

#	Time	Username	Problem	Language	Result	Execution time	Memory
1203017		DeltaStruct	Finding Routers (IOI20_routers)	C++20	100 / 100	2 ms	328 KiB

routers

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

std::vector<int> find_routers(int l, int n, int q){
  vector<int> A(n),L(n-1),R(n-1,l);
  while(true){
    map<int,int> M; for (int i(0);i < n-1;++i) if (R[i]-L[i]>1) M[(L[i]+R[i])/2] = -1;
    //for (int i(0);i < n-1;++i) cout << i << ' ' << L[i] << ' ' << R[i] << endl;
    if (M.empty()) break;
    for (auto& [a,b]:M) b = use_detector(a);
    for (int i(0);i < n-1;++i) if (R[i]-L[i]>1){
      if (M[(L[i]+R[i])/2]<=i) L[i] = (L[i]+R[i])/2;
      else R[i] = (L[i]+R[i])/2;
    }
  }
  for (int i(1);i < n;++i) A[i] = 2*L[i-1]-A[i-1];
  return A;
}

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