| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 456461 |
2021-08-06T20:19:30 Z |
Antekb |
Sob (COCI19_sob) |
C++14 |
|
83 ms |
31248 KB |
#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<A.size(); i++){
if(i+t==A.size() || (B[i]&(1<<k))){
for(int j=0; j<t;j++){
B2.push_back(B[i+j]);
}
for(int j=i+t; j<A.size(); j++){
B1.push_back(B[j]);
}
break;
}
else B1.push_back(B[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());
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
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]);
| ~^~~~~~~~~
sob.cpp:32:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
32 | for(int i=0; i<A.size(); i++){
| ~^~~~~~~~~
sob.cpp:33:10: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
33 | if(i+t==A.size() || (B[i]&(1<<k))){
| ~~~^~~~~~~~~~
sob.cpp:37:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
37 | for(int j=i+t; j<A.size(); j++){
| ~^~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
204 KB |
Output is correct |
| 2 |
Correct |
1 ms |
204 KB |
Output is correct |
| 3 |
Correct |
0 ms |
204 KB |
Output is correct |
| 4 |
Correct |
83 ms |
31248 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
3 ms |
972 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
0 ms |
204 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
204 KB |
Output is correct |
| 2 |
Correct |
1 ms |
204 KB |
Output is correct |
| 3 |
Correct |
0 ms |
204 KB |
Output is correct |
| 4 |
Correct |
83 ms |
31248 KB |
Output is correct |
| 5 |
Incorrect |
3 ms |
972 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
