Submission #1006613

#TimeUsernameProblemLanguageResultExecution timeMemory
1006613shenfe1Nice sequence (IZhO18_sequence)C++17
0 / 100
2 ms6748 KiB
#include <bits/stdc++.h> #define ff first #define ss second #define ll long long #define lb lower_bound #define pii pair<int,int> #define pll pair<ll,ll> #define F first #define S second #define ld long double #define pb push_back #define all(v) v.begin(),v.end() #define in insert #define sz(s) (int)s.size() #define int ll #define ppb pop_back #define mem(a,i) memset(a,i,sizeof(a)) using namespace std; const int MAX=2e5+100; const int inf=1e18; const int dx[4]={1,0,-1,0}; const int dy[4]={0,1,0,-1}; int n,m; int p[MAX]; int use[MAX]; bool ok; vector<int> g[MAX]; vector<int> top; void dfs(int v){ use[v]=1; for(auto to:g[v]){ if(!use[to])dfs(to); else if(use[to]==1){ ok=0; } } top.pb(v); use[v]=2; } bool check(int mid){ ok=1; top.clear(); for(int i=0;i<=mid;i++)g[i].clear(),use[i]=0; for(int i=m;i<=mid;i++){ g[i-m].pb(i); } for(int i=n;i<=mid;i++){ g[i].pb(i-n); } for(int i=0;i<=mid;i++){ if(!use[i]){ dfs(i); } } if(!ok)return 0; for(int i=0;i<=mid;i++){ p[top[i]]=i; } for(int i=1;i<=mid;i++)p[i]-=p[0]; p[0]=0; return 1; } void solve(){ cin>>n>>m; bool ok=0; if(n<m){ ok=1; swap(n,m); } int l=1,r=lcm(n,m),res=0; while(l<=r){ int mid=(l+r)/2; if(check(mid)){ l=mid+1; res=mid; } else r=mid-1; } check(res); for(int i=res;i>=1;i--)p[i]-=p[i-1]; if(ok)for(int i=1;i<=res;i++)p[i]=-p[i]; cout<<res<<'\n'; for(int i=1;i<=res;i++)cout<<p[i]<<" "; cout<<"\n"; } // #ifdef LOCAL signed main(){ // freopen("pushabox.in","r",stdin); // freopen("pushabox.out","w",stdout); ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); int t=1; cin>>t; while(t--)solve(); } // #endif
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...