제출 #1254551

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1254551		turmax	Minerals (JOI19_minerals)	C++20	100 / 100	603 ms	18144 KiB

minerals

#ifndef LOCAL
#include "minerals.h"
#endif
#include <bits/stdc++.h>
using namespace std;
#define app push_back
#define all(x) x.begin(), x.end()
#ifdef LOCAL
#define debug(...) [](auto...a){ ((cout << a << ' '), ...) << endl; }(#__VA_ARGS__, ":", __VA_ARGS__)
#define debugv(v) do { cout << #v << ": "; for (auto x : v) cout << x << ' '; cout << endl; } while(0)
#else
#define debug(...)
#define debugv(v)
#endif
#ifdef LOCAL
mt19937 rng(chrono::system_clock::now().time_since_epoch().count());
#define count cou
constexpr int MAX_N = 50000;
constexpr int MAX_CALLS = 2e6; /// check that <=1e6 visually

namespace {

void WrongAnswer(int code) {
  printf("Wrong Answer [%d]\n", code);
  exit(0);
}

int N;
int counterpart[2 * MAX_N + 1];

int num_queries;
int num_kinds;
int on[2 * MAX_N + 1];
int count[2 * MAX_N + 1];

int num_answers;
int answer[2 * MAX_N + 1];

}  // namespace

int Query(int x) {
  if (!(1 <= x && x <= 2 * N)) {
    WrongAnswer(1);
  }
  if (++num_queries > MAX_CALLS) {
    WrongAnswer(2);
  }
  const int type = std::min(x, counterpart[x]);
  if (on[x]) {
    --on[x];
    --count[type];
    if (count[type] == 0) {
      --num_kinds;
    }
  } else {
    ++on[x];
    ++count[type];
    if (count[type] == 1) {
      ++num_kinds;
    }
  }
  return num_kinds;
}

void Answer(int a, int b) {
  if (++num_answers > N) {
    WrongAnswer(6);
  }
  if (!(1 <= a && a <= 2 * N && 1 <= b && b <= 2 * N)) {
    WrongAnswer(3);
  }
  if (answer[a] != 0) {
    WrongAnswer(4);
  }
  answer[a] = b;
  if (answer[b] != 0) {
    WrongAnswer(4);
  }
  answer[b] = a;
  if (!(counterpart[a] == b && counterpart[b] == a)) {
    WrongAnswer(5);
  }
}
#endif
const int maxn=1e5;
int shu[maxn];
bool ok[maxn];
int lst=0;
bool que(int i,bool rev) {
    //debug(i,rev);
    ok[i]=(ok[i]^1);
    int ne=Query(shu[i]+1);
    //debug(ne);
    bool ans;
    if(ok[i]==0) {
        ans=(ne==lst);
    }
    else {
        ans=(ne==lst);
    }
    lst=ne;
    //debug(ans^rev);
    return ans^rev;
}
mt19937 rnd;
void Solve(int N) {
    iota(shu,shu+2*N,0);shuffle(shu,shu+2*N,mt19937(228));
    int zx[2*N]={0};
    bool rev=false;
    for(int i=0;i<2*N;++i) {
        bool h=que(i,rev);
        if(h) {zx[i]=1;}
        else {zx[i]=0;}
    }
    rev^=1;
    vector<int> zeros;for(int i=0;i<2*N;++i) {if(!zx[i]) zeros.app(i);}
    //debugv(zeros);
    int le[2*N]={0};int ri[2*N]={0};
    for(int i=0;i<2*N;++i) {
        if(zx[i]) {
            ri[i]=upper_bound(all(zeros),i)-zeros.begin();
        }
    }
    vector<bool> ban(2*N);
    vector<vector<int> > positions;
    vector<vector<int> > answers;
    auto possible=[&](int le,int ri) {
        if(le>=ri) {return false;}
        if(ban[le]^ban[ri]) {return false;}
        for(int i=0;i<positions.size();++i) {
            if(positions[i][le]<positions[i][ri] && (answers[i][le]!=0 || answers[i][ri]!=1)) {return false;}
            if(positions[i][ri]<positions[i][le] && (answers[i][le]!=1 || answers[i][ri]!=0)) {return false;}
        }
        return true;
    };
    vector<int> what_to_ask[zeros.size()];
    int cnt[2*N+1]={0};
    int mi[2*N]={0};
    while(true) {
            for(int iter=0;iter<7;++iter) {
            for(int i=0;i<2*N;++i) {
                if(zx[i]) {
                    if(ri[i]-le[i]>1) {
                        while(ban[zeros[le[i]]] || !possible(zeros[le[i]],i)) {
                            ++le[i];
                        }
                        while(ban[zeros[ri[i]-1]] || !possible(zeros[ri[i]-1],i)) {
                            --ri[i];
                        }
                    }
                }
            }
            fill(cnt,cnt+2*N+1,0);
            for(int i=0;i<2*N;++i) {
                if(zx[i]) {
                    cnt[le[i]]++;cnt[ri[i]]--;
                }
            }
            for(int i=0;i<2*N;++i) {
                cnt[i+1]+=cnt[i];
            }
            for(int i=0;i<2*N;++i) {
                if(zx[i] && !ban[i]) {
                    if(ri[i]-le[i]>1 && ri[i]-le[i]<100) {
                        for(int j=le[i];j<ri[i];++j) {
                            if(cnt[j]==1) {
                                le[i]=j;ri[i]=j+1;
                                break;
                            }
                        }
                    }
                }
            }
            for(int i=0;i<2*N;++i) {
                if(zx[i]) {
                    if(ri[i]-le[i]==1) {
                        ban[i]=1;ban[zeros[le[i]]]=1;
                    }
                }
            }
            }
        bool okk=1;
        for(int i=0;i<2*N;++i) {
            if(zx[i]==1) {
                if(ri[i]-le[i]>1) {
                    okk=0;
                }
            }
        }
        if(okk) {
            vector<pair<int,int> > ans;
            for(int i=0;i<2*N;++i) {
                if(zx[i]==1) {
                    ans.app({zeros[le[i]],i});
                }
            }
            for(auto [i,j]:ans) {
                Answer(shu[i]+1,shu[j]+1);
            }
            return;
        }
        for(int i=0;i<zeros.size();++i) what_to_ask[i].clear();
        for(int i=0;i<2*N;++i) {
            if(zx[i]==1) {
                mi[i]=(le[i]+ri[i])/2;
                if(!ban[i] && ri[i]-le[i]>1 && ri[i]-le[i]<100) {
                    vector<int> la;
                    //debug(possible(zeros[le[i]],i));
                    for(int ii=le[i];ii<ri[i];++ii) {
                        if(possible(zeros[ii],i)) {
                            la.app(ii);
                        }
                    }
                    assert(!la.empty());
                    mi[i]=(rnd()%2==0 ? la[la.size()/2] : la[(la.size()+1)/2]);
                }
                int mid=mi[i];
                what_to_ask[mid].app(i);
            }
        }
        vector<int> pos(2*N);vector<int> ans(2*N);
        int cur=0;
        for(int i=0;i<zeros.size();++i) {
            for(int j:what_to_ask[i]) {
                if(ban[j]) continue;
                int h=que(j,rev);
                pos[j]=cur;ans[j]=h;++cur;
                int mid=mi[j];
                if(h) {
                    ri[j]=mid;
                }
                else{
                    le[j]=mid;
                }
            }
            if(!ban[zeros[i]]) {int h=que(zeros[i],rev);pos[zeros[i]]=cur;ans[zeros[i]]=h;++cur;} ///???
        }
        positions.app(pos);answers.app(ans);
        rev^=1;
    }
    assert(false);
}
#ifdef LOCAL
int main() {
  /*if (scanf("%d", &N) != 1) {
    fprintf(stderr, "Error while reading input\n");
    exit(1);
  }
  for (int i = 1; i <= N; ++i) {
    int x, y;
    if (scanf("%d%d", &x, &y) != 2) {
      fprintf(stderr, "Error while reading input\n");
      exit(1);
    }
    counterpart[x] = y;
    counterpart[y] = x;
  }*/
  for(int cyc=0;cyc<20;++cyc) {
  N=47200;
  fill(on,on+2 * MAX_N + 1,0);fill(count,count+2 * MAX_N + 1,0);num_queries=0;num_kinds=0;num_answers=0;fill(answer,answer+2 * MAX_N + 1,0);
  lst=0;fill(ok,ok+maxn,0);
  vector<int> arr(2*N);iota(all(arr),1LL);
  shuffle(all(arr),mt19937(rng()));
  for(int i=0;i<N;++i) {
    int x=arr[2*i];int y=arr[2*i+1];
    //debug(x,y);
    counterpart[x] = y;
    counterpart[y] = x;
  }
  Solve(N);
  if (num_answers != N) {
    WrongAnswer(6);
  }
  printf("Accepted: %d\n", num_queries);
  }
  return 0;
}
#endif

• 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: 10 / 10