Submission #456465

#	Time	Username	Problem	Language	Result	Execution time	Memory
456465		Antekb	Sob (COCI19_sob)	C++14	110 / 110	177 ms	69684 KiB

sob

#include<bits/stdc++.h>
using namespace std;
vector<pair<int, int> > ans;
void solve(int k, vector<int> A, vector<int> B){
	assert(A.size()==B.size());
	//cout<<k<<"a"<<A.size()<<"\n";
	//assert(A.size()<=(1<<k));
	if(A.size()==(1<<k)){
		/*for(int i:A)cout<<i<<"|"<<i%(1<<k)<<" ";
			cout<<"\n";
		for(int i:B)cout<<i<<"|"<<i%(1<<k)<<" ";
			cout<<"\n";
		cout<<(1<<k)<<"\n";*/
		for(int i=0; i<B.size(); i++){
			ans.push_back({A[(B[i]&((1<<k)-1))], B[i]});
			//cout<<A[((1<<k)-1)^(B[i]&((1<<k)-1))]<<" "<<B[i]<<"\n";
			//cout<<(A[B.size()-1-(B[i]&(B.size()-1))]&B[i])<<"\n";
		}
	}
	else if(A.size()<(1<<k))solve(k-1, A, B);
	else{
		/*for(int i:A)cout<<i<<" ";
			cout<<"\n";
		for(int i:B)cout<<i<<" ";
			cout<<"\n";*/
		assert((1<<k)<A.size());
		assert((1<<(k+1))>A.size());
		vector<int> A1, A2, B1, B2;
		for(int i=0; i<(1<<k);i++)A1.push_back(A[i]);
		for(int i=(1<<k); i<A.size();i++)A2.push_back(A[i]);
		int t=A.size()-(1<<k);
		for(int i=0; i<t; i++){
			if(B[i]&(1<<k)){
				B1.push_back(B[i+(1<<k)]);
				B2.push_back(B[i]);
			}
			else{
				B2.push_back(B[i+(1<<k)]);
				B1.push_back(B[i]);
			}
		}
		for(int i=0; i<(1<<k)-t; i++){
			B1.push_back(B[t+i]);
		}
		solve(k, A1, B1);
		solve(k-1, A2, B2);
	}
}
int main(){
	int n, m;
	cin>>n>>m;
	vector<int> A, B;
	for(int i=0; i<n; i++)A.push_back(i), B.push_back(m+i);
	solve(30, A, B);
	sort(ans.begin(), ans.end());
	assert(ans.size()==n);
	for(int i=1; i<n; i++)assert(ans[i].first>ans[i-1].first);
	for(int i=0; i<n; i++)assert((ans[i].first&ans[i].second)==ans[i].first);
	for(int i=0; i<n; i++)cout<<ans[i].first<<" "<<ans[i].second<<"\n";
}

Compilation message (stderr)

sob.cpp: In function 'void solve(int, std::vector<int>, std::vector<int>)':
sob.cpp:8:13: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
    8 |  if(A.size()==(1<<k)){
      |     ~~~~~~~~^~~~~~~~
sob.cpp:14:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   14 |   for(int i=0; i<B.size(); i++){
      |                ~^~~~~~~~~
sob.cpp:20:18: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   20 |  else if(A.size()<(1<<k))solve(k-1, A, B);
      |          ~~~~~~~~^~~~~~~
In file included from /usr/include/c++/10/cassert:44,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:33,
                 from sob.cpp:1:
sob.cpp:26:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   26 |   assert((1<<k)<A.size());
      |          ~~~~~~^~~~~~~~~
sob.cpp:27:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   27 |   assert((1<<(k+1))>A.size());
      |          ~~~~~~~~~~^~~~~~~~~
sob.cpp:30:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   30 |   for(int i=(1<<k); i<A.size();i++)A2.push_back(A[i]);
      |                     ~^~~~~~~~~
In file included from /usr/include/c++/10/cassert:44,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:33,
                 from sob.cpp:1:
sob.cpp: In function 'int main()':
sob.cpp:56:19: warning: comparison of integer expressions of different signedness: 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   56 |  assert(ans.size()==n);
      |         ~~~~~~~~~~^~~

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