Submission #887417

#	Time	Username	Problem	Language	Result	Execution time	Memory
887417		pcc	Nice sequence (IZhO18_sequence)	C++14	100 / 100	1085 ms	53324 KiB

sequence

#include <bits/stdc++.h>
using namespace std;

#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,popcnt")

#define ll long long
#define pll pair<ll,ll>
#define pii pair<int,int>
#define fs first
#define sc second
#define tlll tuple<ll,ll,ll>

const int mxn = 4e5+10;
int n,m;
vector<int> paths[mxn];
int deg[mxn];
queue<int> q;
int arr[mxn];
map<pii,int> mp;

inline bool check(int tar){
	for(int i = 0;i+n<=tar;i++){
		paths[i+n].push_back(i);
		deg[i]++;
	}
	for(int i = 0;i+m<=tar;i++){
		paths[i].push_back(i+m);
		deg[i+m]++;
	}
	for(int i = 0;i<=tar;i++){
		if(!deg[i])q.push(i);
	}
	int p = 0;
	while(!q.empty()){
		auto now = q.front();
		arr[now] = ++p;
		q.pop();
		for(auto nxt:paths[now]){
			deg[nxt]--;
			if(!deg[nxt])q.push(nxt);
		}
	}
	for(int i = 0;i<=tar;i++){
		paths[i].clear();
		deg[i] = 0;
	}
	//cout<<tar<<":"<<p<<endl;
	return p == tar+1;
}

inline void solve(){
	cin>>n>>m;
	int l,r;
	l = r = n+m-__gcd(n,m)-1;
	while(l != r){
		int mid = (l+r+1)>>1;
		if(check(mid))l = mid;
		else r = mid-1;
	}
	check(l);
	cout<<l<<'\n';
	//for(int i = 1;i<=l;i++)cout<<arr[i]<<' ';cout<<endl;
	mp[make_pair(n,m)] = l;
	for(int i  =1;i<=l;i++)cout<<arr[i]-arr[i-1]<<' ';cout<<'\n';
	return;
}

int main(){
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	int t;cin>>t;
	while(t--)solve();
}

Compilation message (stderr)

sequence.cpp: In function 'void solve()':
sequence.cpp:65:2: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   65 |  for(int i  =1;i<=l;i++)cout<<arr[i]-arr[i-1]<<' ';cout<<'\n';
      |  ^~~
sequence.cpp:65:52: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   65 |  for(int i  =1;i<=l;i++)cout<<arr[i]-arr[i-1]<<' ';cout<<'\n';
      |                                                    ^~~~

• Subtask 1: 6 / 6
• Subtask 2: 9 / 9
• Subtask 3: 14 / 14
• Subtask 4: 15 / 15
• Subtask 5: 14 / 14
• Subtask 6: 18 / 18
• Subtask 7: 24 / 24