Submission #1301500

#	Time	Username	Problem	Language	Result	Execution time	Memory
1301500		noyancanturk	Minerals (JOI19_minerals)	C++20	90 / 100	626 ms	6076 KiB

minerals

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

#define pb push_back

const int lim=5e4;

int curval=0;

int p[2*lim];

int query(int x){
  return Query(p[x]+1);
}

int delta(int x){
  int past=curval;
  curval=query(x);
  return curval-past;
}

void answer(int x,int y){
  // cerr<<x<<' '<<y<<'\n';
  Answer(p[x]+1,p[y]+1);
}

struct{
  int tree[2*lim];
  void update(int p,int val){
    p+=5;
    while(p<2*lim){
      tree[p]+=val;
      p+=p&-p;
    }
  }
  int query(int p){
    p+=5;
    int ans=0;
    while(p){
      ans+=tree[p];
      p-=p&-p;
    }
    return ans;
  }
  int walk(int val){
    int p=0;
    for(int i=20;0<=i;i--){
      if(p+(1<<i)<2*lim&&tree[p+(1<<i)]<val){
        val-=tree[p+(1<<i)];
        p+=(1<<i);
      }
    }
    return p+1-5;
  }
}fw;

void Solve(int n) {
  srand(chrono::high_resolution_clock().now().time_since_epoch().count());
  for(int i=0;i<2*n;i++){
    p[i]=i;
  }
  random_shuffle(p,p+2*n);
  int l[2*n]{},r[2*n]{};
  vector<int>down,up;
  for(int i=0;i<2*n;i++){
    if(down.size()==n||!delta(i)){
      up.pb(i);
      r[i]=down.size()-1;
    }else{
      fw.update(down.size(),1);
      down.pb(i);
    }
  }
  int cnt=0,ty=0;
  while(cnt<n){
    vector<int>v[n];
    for(int tr=1;tr;){
      tr=0;
      for(int i=0;i<n;i++){
        if(l[up[i]]==-1){
          continue;
        }
        l[up[i]]=fw.walk(fw.query(l[up[i]]-1)+1);
        r[up[i]]=fw.walk(fw.query(r[up[i]]));
        if(l[up[i]]==r[up[i]]){
          answer(up[i],down[l[up[i]]]);
          fw.update(l[up[i]],-1);
          l[down[l[up[i]]]]=-1;
          l[up[i]]=-1;
          cnt++;
          tr=1;
        }
      }
    }
    for(int i=0;i<n;i++){
      if(l[up[i]]==-1){
        continue;
      }
      int mid=fw.walk(fw.query(l[up[i]])+fw.query(r[up[i]])>>1);
      v[mid].pb(i);
    }
    if(cnt==n)break;
    if(!ty){
      for(int i=n-1;0<=i;i--){
        for(int tr=1;tr;){
          tr=0;
          for(int j:v[i]){
            if(l[up[j]]==-1)continue;
            l[up[j]]=fw.walk(fw.query(l[up[j]]-1)+1);
            r[up[j]]=fw.walk(fw.query(r[up[j]]));
            if(l[up[j]]==r[up[j]]){
              answer(up[j],down[l[up[j]]]);
              fw.update(l[up[j]],-1);
              l[down[l[up[j]]]]=-1;
              l[up[j]]=-1;
              cnt++;
              tr=1;
            }
          }
        }
        for(int j:v[i]){
          if(l[up[j]]==-1)continue;
          l[up[j]]=fw.walk(fw.query(l[up[j]]-1)+1);
          r[up[j]]=fw.walk(fw.query(r[up[j]]));
          if(l[up[j]]==r[up[j]]){
            answer(up[j],down[l[up[j]]]);
            fw.update(l[up[j]],-1);
            l[down[l[up[j]]]]=-1;
            l[up[j]]=-1;
            cnt++;
            continue;
          }
          int mid=fw.walk(fw.query(l[up[j]])+fw.query(r[up[j]])>>1);
          if(mid<i){
            v[mid].pb(j);
            continue;
          }
          if(r[up[j]]<i||i<l[up[j]])continue;
          if(delta(up[j])){
            l[up[j]]=i+1;
          }else{
            r[up[j]]=i;
          }
          l[up[j]]=fw.walk(fw.query(l[up[j]]-1)+1);
          r[up[j]]=fw.walk(fw.query(r[up[j]]));
          if(l[up[j]]==r[up[j]]){
            answer(up[j],down[l[up[j]]]);
            fw.update(l[up[j]],-1);
            l[down[l[up[j]]]]=-1;
            l[up[j]]=-1;
            cnt++;
          }else{
            int mid=fw.walk(fw.query(l[up[j]])+fw.query(r[up[j]])>>1);
            v[mid].pb(j);
          }
        }
        if(i&&l[down[i]]!=-1){
          delta(down[i]);
        }
      }
    }else{
      for(int i=0;i<n;i++){
        for(int tr=1;tr;){
          tr=0;
          for(int j:v[i]){
            if(l[up[j]]==-1)continue;
            l[up[j]]=fw.walk(fw.query(l[up[j]]-1)+1);
            r[up[j]]=fw.walk(fw.query(r[up[j]]));
            if(l[up[j]]==r[up[j]]){
              answer(up[j],down[l[up[j]]]);
              fw.update(l[up[j]],-1);
              l[down[l[up[j]]]]=-1;
              l[up[j]]=-1;
              cnt++;
              tr=1;
            }
          }
        }
        if(i&&l[down[i]]!=-1){
          delta(down[i]);
        }
        for(int j:v[i]){
          if(l[up[j]]==-1)continue;
          l[up[j]]=fw.walk(fw.query(l[up[j]]-1)+1);
          r[up[j]]=fw.walk(fw.query(r[up[j]]));
          if(l[up[j]]==r[up[j]]){
            answer(up[j],down[l[up[j]]]);
            fw.update(l[up[j]],-1);
            l[down[l[up[j]]]]=-1;
            l[up[j]]=-1;
            cnt++;
            continue;
          }
          int mid=fw.walk(fw.query(l[up[j]])+fw.query(r[up[j]])>>1);
          if(i<mid){
            v[mid].pb(j);
            continue;
          }
          if(r[up[j]]<i||i<l[up[j]])continue;
          if(delta(up[j])){
            l[up[j]]=i+1;
          }else{
            r[up[j]]=i;
          }
          l[up[j]]=fw.walk(fw.query(l[up[j]]-1)+1);
          r[up[j]]=fw.walk(fw.query(r[up[j]]));
          if(l[up[j]]==r[up[j]]){
            answer(up[j],down[l[up[j]]]);
            fw.update(l[up[j]],-1);
            l[down[l[up[j]]]]=-1;
            l[up[j]]=-1;
            cnt++;
          }else{
            int mid=fw.walk(fw.query(l[up[j]])+fw.query(r[up[j]])>>1);
            v[mid].pb(j);
          }
        }
      }
    }
    ty^=1;
  }
}

Compilation message (stderr)

minerals.cpp: In function 'void Solve(int)':
minerals.cpp:63:17: warning: 'void std::random_shuffle(_RAIter, _RAIter) [with _RAIter = int*]' is deprecated: use 'std::shuffle' instead [-Wdeprecated-declarations]
   63 |   random_shuffle(p,p+2*n);
      |   ~~~~~~~~~~~~~~^~~~~~~~~
In file included from /usr/include/c++/13/algorithm:61,
                 from /usr/include/x86_64-linux-gnu/c++/13/bits/stdc++.h:51,
                 from minerals.cpp:2:
/usr/include/c++/13/bits/stl_algo.h:4581:5: note: declared here
 4581 |     random_shuffle(_RandomAccessIterator __first, _RandomAccessIterator __last)
      |     ^~~~~~~~~~~~~~

• Subtask 1: 6 / 6
• Subtask 2: 25 / 25
• Subtask 3: 9 / 9
• Subtask 4: 30 / 30
• Subtask 5: 5 / 5
• Subtask 6: 5 / 5
• Subtask 7: 5 / 5
• Subtask 8: 5 / 5
• Subtask 9: 0 / 10