This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
#define maxn 200010
using namespace std;
int n, m, t, prefS[maxn], res[maxn], ans;
vector<int> topV;
bool was[maxn];
void topSort(int x, int mx){
// prefS[x+n] < prefS[x], prefS[x-m] < prefS[x]
was[x] = 1;
if(x+n <= mx and !was[x+n]){
topSort(x+n, mx);
}
if(x-m >= 0 and !was[x-m]){
topSort(x-m, mx);
}
topV.push_back(x);
}
bool ok(int mx){
topV.clear();
for(int i = 0; i <= mx; ++i){
//cerr << was[i] << ' ';
if(!was[i]){
topSort(i, mx);
}
}
for(int i = 0; i <= mx; ++i){
prefS[topV[i]] = i;
was[i] = 0;
}
for(int i = 0; i <= mx; ++i){
if( (i+n<=mx and prefS[i] < prefS[i+n]) or (i-m >= 0 and prefS[i-m] > prefS[i]) ){
return 0;
}
}
for(int i = 1 ;i <mx+1;++i){
res[i] = prefS[i]-prefS[i-1];
}
return 1;
}
int main(){
ios_base::sync_with_stdio(0);
cout.tie(0);
cin.tie(0);
cin >> t;
while(t--){
cin >> n >> m;
ans = 0;
int l = 0, r = maxn;
while(l <= r){
int mid = (l+r)/2;
//cerr<<mid<<'\n';
if(ok(mid)){
l=mid+1;
ans = max(ans, mid);
} else {
r = mid-1;
}
}
ok(ans);
cout << ans<<'\n';
for(int i = 1; i <= ans; ++i){
cout << res[i] << ' ';
}
cout << '\n';
}
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |