QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#239977 | #7688. Alea Iacta Est | ucup-team197# | WA | 182ms | 111136kb | C++14 | 2.6kb | 2023-11-05 01:56:13 | 2023-11-05 01:56:13 |
Judging History
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)