Submission #1230269

#	Time	Username	Problem	Language	Result	Execution time	Memory
1230269		warrenn	Finding Routers (IOI20_routers)	C++20	100 / 100	1 ms	584 KiB

routers

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


vector<int> find_routers(int leng, int n, int qu) {
    pair<int,int>simpan[n+1];
    int udh[leng+1];
    memset(udh,-1,sizeof udh);

    int lst=1;
    for(int q=0;q<n-1;q++){
      int l=0;
      int r=leng;
      int hmm=-1;
      while(l<=r){
        int mid=(l+r)/2;
        int idx;
        if(udh[mid]!=-1){
          idx=udh[mid];
        }
        else{
          idx=use_detector(mid);
          udh[mid]=idx;
        }
       
        if(idx>q){
          r=mid-1;
        }
        else if(idx==q){
          hmm=mid;
          l=mid+1;
        }
        else{
          l=mid+1;
        }
      }
      simpan[q]={lst,hmm};
      //cout<<lst<<" "<<hmm<<" "<<q<<endl;
      lst=hmm+1;
    }
    simpan[n-1]={lst,leng};
    vector<int>ans;
    ans.push_back(0);
    for(int q=1;q<n;q++){
      pair<int,int>prev=simpan[q-1];
      pair<int,int>cur=simpan[q];
      int sblm=ans.back();

      int hihi=cur.first-sblm+prev.second-1;
      ans.push_back(hihi);
    }
    return ans;
  }

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