QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#239977#7688. Alea Iacta Estucup-team197#WA 182ms111136kbC++142.6kb2023-11-05 01:56:132023-11-05 01:56:13

Judging History

你现在查看的是最新测评结果

  • [2023-11-05 01:56:13]
  • 评测
  • 测评结果:WA
  • 用时:182ms
  • 内存:111136kb
  • [2023-11-05 01:56:13]
  • 提交

answer

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define fi first
#define se second
const int N=3e6+5;
const int iu=1e6;
vector<int>pf[N];
ll n,m;
int sz=0;
ll v[N];
void gen(vector<pair<ll,ll> >&g,int id,ll cur){
	if(id==g.size()){
		v[++sz]=cur;
		return;
	}
	for(int i=0; i<g[id].fi ;i++){
		ll dx=i*g[id].se;
		gen(g,id+1,cur+dx);
	}
}
ll gcd(ll x,ll y){
	if(y==0) return x;
	return gcd(y,x%y);
}
void dumb(){
	cout << 2*n << ' ';
	for(int i=1; i<=n ;i++) cout << i << ' ' << i << ' ';
	cout << '\n';
	cout << m << ' ';
	for(int i=1; i<=m ;i++) cout << i << ' ';
	cout << '\n';
}
ll test_dumb(){
	return 2*n+m;
}
void solve(){
	cin >> n >> m;
	if(n==1 && m!=1 || n!=1 && m==1){
		cout << m << ' ';
		for(int i=1; i<=m ;i++) cout << i << ' ';
		cout << '\n';
		cout << n << ' ';
		for(int i=1; i<=n ;i++) cout << i << ' ';
		cout << '\n';
		return;
	}
	if(n>m) swap(n,m);
	if(n==1 && pf[m].size()<=1){
		dumb();
		return;
	}
	ll xs=n;
	for(ll s=n+1; s<=m ;s++){
		if(s*s>n*m) break;
		if(n*m%s==0) xs=s;
	}
	ll g=gcd(n,m);
	if(n==m && pf[n].size()==1) g=1;
	vector<pair<ll,ll> >gl,gr;
	if(xs==n && g!=1){//score = n+m
		ll p=pf[g][0];
		for(int i=0; i<pf[n].size() ;i++){
			if(pf[n][i]==p){
				swap(pf[n][0],pf[n][i]);
				break;
			}
		}
		{
			ll step=1;
			for(auto c:pf[n]){
				gl.push_back({c,step});
				step*=c;
			}
		}
		for(int i=0; i<pf[m].size() ;i++){
			if(pf[m][i]==p){
				swap(pf[m][0],pf[m][i]);
				break;
			}
		}
		swap(pf[m][0],pf[m].back());
		{
			ll step=1;
			for(auto c:pf[m]){
				gr.push_back({c,step});
				step*=c;
			}
		}
		swap(gl[0],gr.back());
	}
	else{
		if(xs==n){
			xs--;
			while(n*m%xs!=0) --xs;
		}
		if(test_dumb()<=xs+(n*m)/xs){
			dumb();
			return;
		}
		vector<pair<ll,ll> >gn;
		{
			ll step=1;
			for(auto c:pf[n]){
				gn.push_back({c,step});
				step*=c;
			}
		}
		{
			ll step=1;
			for(auto c:pf[m]){
				gn.push_back({c,step});
				step*=c;
			}
		}
		for(auto c:gn){
			if(xs%c.fi==0){
				xs/=c.fi;
				gl.push_back(c);
			}
			else gr.push_back(c);
		}
	}
	sz=0;
	gen(gl,0,0);
	cout << sz << ' ';
	for(int i=1; i<=sz ;i++) cout << v[i]+1 << ' ';
	cout << '\n';
	sz=0;
	gen(gr,0,0);
	cout << sz << ' ';
	for(int i=1; i<=sz ;i++) cout << v[i]+1 << ' ';
	cout << '\n';
}
int main(){
	ios::sync_with_stdio(false);cin.tie(0);
	for(int i=2; i<=iu ;i++){
		if(!pf[i].empty()) continue;
		for(int j=i; j<=iu ;j+=i){
			int z=j;
			while(z%i==0){
				z/=i;
				pf[j].push_back(i);
			}
		}
	}
	int t;cin >> t;
	while(t--) solve();
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 0
Wrong Answer
time: 182ms
memory: 111136kb

input:

3
2 8
1 9
2 9

output:

4 1 2 2 3 
4 1 5 3 7 
9 1 2 3 4 5 6 7 8 9 
1 1 
3 1 2 3 
6 1 4 7 2 5 8 

result:

wrong answer Same as input (test case 2)