Submission #439910

#	Time	Username	Problem	Language	Result	Execution time	Memory
439910		hivakarami	Sob (COCI19_sob)	C++14	110 / 110	360 ms	26384 KiB

sob

#include<bits/stdc++.h>

 
using namespace std;
 
typedef long long int ll;
typedef long double ld;
#define f first
#define s second
#define pb push_back
#define pii pair<int, int>

 
const int N = 2e5 + 5;
const ll inf = 1e9 * 600;
const ll mod = 1e9 + 7;
const int lg = 30;


vector<pii> v[2], t[4];

void solve(int l, int r)
{
	if(l+1 == r)
	{
		cout << v[0][l].s << ' ' << v[1][l].s << '\n';
		return;
	}
		
	t[0].clear();
	t[1].clear();
	t[2].clear();
	t[3].clear();
	
	
	for(int i = l; i < r; i++)
	{
		if(v[0][i].f%2 == 0)
			t[0].pb({v[0][i].f/2, v[0][i].s});
		else
			t[2].pb({v[0][i].f/2, v[0][i].s});
	}
	
	if(t[0].size() > t[2].size() && v[1][l].f % 2 == 1)
		v[1][l].f--;
		
	for(int i = l; i < r; i++)
	{
		if(v[1][i].f%2 == 0)
			t[1].pb({v[1][i].f/2, v[1][i].s});
		else
			t[3].pb({v[1][i].f/2, v[1][i].s});
	}

	int sz0 = t[0].size();

	for(int i = l; i < l+sz0; i++)
	{
		v[0][i] = t[0][i-l];
		v[1][i] = t[1][i-l];
	}

	for(int i = l+sz0; i < r; i++)
	{
		v[0][i] = t[2][i-l-sz0];
		v[1][i] = t[3][i-l-sz0];
	}
		
	
	//cout << l << ' ' << r << endl;
	
	solve(l, l+sz0);
	solve(l+sz0, r);
	
}





int main()
{
    
    ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0);	

	
	int n, m;
	cin >> n >> m;
	for(int i = 0; i < n; i++)
		v[0].pb({i, i});
	
	for(int i = m; i < m+n; i++)
		v[1].pb({i, i});

	solve(0, n);
		
	


	return 0;
}

 

 

 
 

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