Submission #250392

# Submission time Handle Problem Language Result Execution time Memory
250392 2020-07-17T16:37:52 Z dvdg6566 Sob (COCI19_sob) C++14
39 / 110
13 ms 10084 KB
#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=100001;
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();
}
# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
3 Correct 0 ms 384 KB Output is correct
4 Runtime error 11 ms 9956 KB Execution killed with signal 11 (could be triggered by violating memory limits)
# Verdict Execution time Memory Grader output
1 Correct 1 ms 512 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 0 ms 384 KB Output is correct
4 Correct 0 ms 384 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Runtime error 13 ms 10084 KB Execution killed with signal 11 (could be triggered by violating memory limits)
7 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Correct 0 ms 384 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
3 Correct 0 ms 384 KB Output is correct
4 Correct 0 ms 384 KB Output is correct
5 Correct 0 ms 384 KB Output is correct
6 Correct 1 ms 384 KB Output is correct
7 Correct 1 ms 384 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
3 Correct 0 ms 384 KB Output is correct
4 Runtime error 11 ms 9956 KB Execution killed with signal 11 (could be triggered by violating memory limits)