# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
1170193 | user736482 | Minerals (JOI19_minerals) | C++20 | 0 ms | 0 KiB |
#include "minerals.h"
#pragma GCC optimize("O3")
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ld long double
#define pb push_back
#define ff first
#define ss second
#define MOD 998244353
#define POT 4194304
#define INF 1000000019
#define INFL 1000000000000000099LL
vector<ll>ind,szuk;
ll gdzie[200000];
void Solve(int n){
ll pop=0;
for(ll i=1;i<=2*n;i++){
if(Query(i)>pop){
pop++;
ind.pb(i);
// cout<<i<<"1 ";
}
else{
szuk.pb(i);
// cout<<i<<"2 ";
}
}
for(ll i=0;i<2*n+7;i++)gdzie[i]=0;
for(ll i=0;i<log2(n);i++){
for(ll j=0;j<n;j++){
if((bool)(j&(1<<i)) ^ (bool)(j&(1<<(i-1))) ^ (i==0)){
if(ind[j]!=-1)
// cout<<j<<" "<<i<<" 1 ";
pop=Query(ind[j]);
}
}
for(ll j=0;j<n;j++){
// cout<<j<<"2 ";
if(gdzie[j]+(1<<i)>n)continue;
if((pop==Query(szuk[j]))){
gdzie[j]+=(1<<i);
}
else{
pop--;
if(i&1)
pop+=2;
}
if(gdzie[j]+(1<<(i+1))){Answer(j,ind[gdzie[j]]);
ind[gdzie[j]]=-1;
}
// cout<<"\n\n";
//cout<<i<<flush;
/* for(ll j=0;j<n;j++){
if(j&(1<<i)){
pop=Query(ind[j]);
}
}
for(ll j=0;j<n;j++){
pop=Query(szuk[j]);
}*/
}
for(ll i=0;i<n;i++){
// Answer(szuk[i],ind[gdzie[i]]);
}
}