| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 346233 | inwbear | Minerals (JOI19_minerals) | C++14 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
//#include "minerals.h"
#include<bits/stdc++.h>
using namespace std;
#define pb push_back
#define all(x) (x).begin(),(x).end()
#define MEM(x,a) memset((x),a,sizeof((x)))
#define F first
#define S second
#define imx INT_MAX
const long long MOD = (long long)(1e9+7);
const long long MMX = (long long)(1e18);
typedef long long LL;
typedef pair<int,int> pii;
int ty[100005],cc[100005],iin[100005],rett,n,k;
void Answer(int x1,int x2)
{
printf("=%d %d\n",x1,x2);
return;
}
int Query(int x1)
{
k++;
if(iin[x1]==1)
{
iin[x1]=0;
cc[ty[x1]]--;
if(cc[ty[x1]]==0)rett--;
}
else
{
iin[x1]=1;
cc[ty[x1]]++;
if(cc[ty[x1]]==1)rett++;
}
return rett;
}
int ls,tp,isin[90005];
vector<int>a,b;
void find_ans(vector<int>A,vector<int>B)
{
int si=A.size(),ch,re;
vector<int>na1,nb1,na2,nb2;
// printf("%d %d\n",A.size(),B.size());
// for(int i=0;i<A.size();i++)
// {
// printf("%d ",A[i]);
// }
// printf("\n");
// for(int i=0;i<B.size();i++)
// {
// printf("%d ",B[i]);
// }
// printf("\n");
// printf("===========\n");
if(A.size()==1)
{
Answer(A[0],B[0]);
return;
}
for(int i=0;i<si/2;i++)
{
if(isin[B[i]]==0)
{
ch=Query(B[i]);
isin[B[i]]=(isin[B[i]]+1)%2;
}
nb1.pb(B[i]);
}
for(int i=(si/2);i<si;i++)
{
if(isin[B[i]]==1)
{
ch=Query(B[i]);
isin[B[i]]=(isin[B[i]]+1)%2;
}
nb2.pb(B[i]);
}
for(int i=0;i<si;i++)
{
re=Query(A[i]);
isin[A[i]]=(isin[A[i]]+1)%2;
if(ch!=re)
{
na2.pb(A[i]);
}
else
{
na1.pb(A[i]);
}
ch=re;
}
find_ans(na1,nb1);
find_ans(na2,nb2);
return;
}
void Solve(int N)
{
for(int i=1;i<=2*N;i++)
{
tp=Query(i);
isin[i]=(isin[i]+1)%2;
if(tp!=ls)
{
a.pb(i);
}
else
{
b.pb(i);
}
ls=tp;
}
find_ans(a,b);
return;
}
int main()
{
freopen("in.txt","r",stdin);
int x1,x2;
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
scanf("%d %d",&x1,&x2);
ty[x1]=i;
ty[x2]=i;
}
Solve(n);
printf("%d",k);
}