Submission #250393

#	Time	Username	Problem	Language	Result	Execution time	Memory
250393		dvdg6566	Sob (COCI19_sob)	C++14	110 / 110	131 ms	22860 KiB

sob

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<ll> vi;
typedef pair<ll,ll> pi;
typedef vector<pi> vpi;
typedef double ld;
#define pb emplace_back
#define mp make_pair
#define lb lower_bound
#define ub upper_bound
#define ALL(x) x.begin(), x.end() 
#define SZ(x) (ll)x.size()
#define f first
#define s second
const ll MAXN=1000001;
const ll MAXK=1000001;
const ll INF = 1e9;
const ll MOD = 1e9+7;

int N,M,a,b,c;
int done[MAXN];
vi A;
vi B;
vi aX;
vi bX;

void doo(){
	while(1){
		if(SZ(A)==1){
			cout<<A[0]<<' '<<B[0]<<'\n';
			return;
		}
		if(SZ(A)==2){
			if(B[1]%2==0)swap(B[0],B[1]);
			if(A[1]%2==0)swap(A[0],A[1]);
			cout<<A[0]<<' '<<B[0]<<'\n';
			cout<<A[1]<<' '<<B[1]<<'\n';
			return;
		}
		aX.clear();bX.clear();
		N=SZ(A);
		for(int i=0;i<N;++i)done[i]=0;
		int l=0;

		int k=N-1;while(k){++l;k=(k>>1);}
		--l;

		for(int i=0;i<N;++i){
			int x=A[i];
			if(x%(1<<(l+1))>=(1<<l))aX.pb(x);
		}

		for(int i=0;i<N;++i){
			int x=B[i];
			int k=(x%(1<<l));
			int t=(x%(1<<(l+1)))/(1<<l);
			if(t)continue;
			done[k]=x;
		}

		for(int i=0;i<N;++i){
			int x=B[i];
			int k=(x%(1<<l));
			int t=(x%(1<<(l+1)))/(1<<l);
			if(!t)continue;
			if(done[k]){bX.pb(x);continue;}
			done[k]=x;
		}
		// cerr<<"H ";for(auto i:bX)cout<<i<<' ';cout<<'\n';
		for(int i=0;i<(1<<l);++i)cout<<A[i]<<' '<<done[i]<<'\n';
		
		swap(A,aX);
		swap(B,bX);
	}
}

int main(){
	ios_base::sync_with_stdio(0);cin.tie(0);
	cin>>N>>M;
	for(int i=0;i<N;++i){
		A.pb(i);B.pb(M+i);
	}
	doo();
}

• Subtask 1: 10 / 10
• Subtask 2: 29 / 29
• Subtask 3: 39 / 39
• Subtask 4: 32 / 32