제출 #1254493

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1254493		turmax	Minerals (JOI19_minerals)	C++20	100 / 100	281 ms	17656 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
#define count cou
constexpr int MAX_N = 50000;
constexpr int MAX_CALLS = 2e6;

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;
}
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;}
        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;
    };
    while(true) {
            for(int i=0;i<2*N;++i) {
                if(zx[i]) {
                    if(ri[i]-le[i]>1) {
                        while(!possible(zeros[le[i]],i)) {
                            ++le[i];
                        }
                        while(!possible(zeros[ri[i]-1],i)) {
                            --ri[i];
                        }
                    }
                }
            }
            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;
        }
        vector<int> what_to_ask[zeros.size()];
        for(int i=0;i<2*N;++i) {
            if(zx[i]==1) {
                int mid=(ri[i]+le[i])/2;
                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=(ri[j]+le[j])/2;
                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;
  }*/
  N=46000;
  vector<int> arr(2*N);iota(all(arr),1LL);
  shuffle(all(arr),mt19937(time(NULL)));
  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