QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#639903 | #6129. Magic Multiplication | hhdhh | WA | 35ms | 5196kb | C++23 | 2.6kb | 2024-10-13 23:47:11 | 2024-10-13 23:47:12 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
// #define endl '\n'
#define rep(i, a, b) for(int i = (a); i <= (b); i++)
#define per(i, a, b) for(int i = (a); i >= (b); i--)
#define rept(i, a, ne) for(int i = (a); ~i ; i=ne[i])
#define debug(x) cout<<#x<<": "<<x<<endl
#define fi first
#define sec second
mt19937_64 rnd(chrono::steady_clock::now().time_since_epoch().count());
typedef long long LL;
typedef long double LD;
typedef unsigned long long ULL;
typedef vector<int> VI;
typedef pair<int,int>PII;
const int N=2e5+10;
LL n,m;
int a[N],b[N];
string s;
LL len;
LL get(int x)
{
return s[x]-'0';
}
bool op(int x)
{
int n2=0;
rep(i,2,n)
a[i]=-1;
a[1]=x;
rep(i,1,len)
{
if(get(i)%x==0)
{
b[++n2]=get(i)/x;
}
else if(i!=len&&get(i)&&(get(i)*10+get(i+1))%x==0)
{
b[++n2]=(get(i)*10+get(i+1))/x;
i++;
}
else
return 0;
if(n2==m)
break;
}
if(n2<m)
return 0;
int n1=0;
int p=0;
int sum=0;
rep(i,1,len)
{
if(sum>n*m)
return 0;
if(sum%m==0)
++n1;
++p;
if(b[p]==0)
{
if(get(i)!=0)
{
return 0;
}
}
else if(get(i)%b[p]==0)
{
if(a[n1]!=-1)
{
if(a[n1]!=get(i)/b[p])
return 0;
}
else
a[n1]=get(i)/b[p];
}
else if(i!=len&&get(i)&&(get(i)*10+get(i+1))%b[p]==0)
{
int y=(get(i)*10+get(i+1));
if(a[n1]!=-1)
{
if(a[n1]!=y/b[p])
return 0;
}
else
a[n1]=y/b[p];
i++;
}
else
return 0;
sum++;
p%=m;
}
if(sum!=n*m)
return 0;
return 1;
}
void slove()
{
cin>>n>>m;
cin>>s;
len=s.size();
s='0'+s;
if(len<n*m||len>n*m*2)
{
cout<<"Impossible"<<endl;
return;
}
rep(i,1,9)
{
if(op(i))
{
rep(i,1,n)
cout<<a[i];
cout<<' ';
rep(i,1,m)
cout<<b[i];
cout<<endl;
return;
}
}
cout<<"Impossible"<<endl;
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
// cout << fixed << setprecision(9);
int t=1;
cin>>t;
while(t--)
{
slove();
}
return 0;
}
//#pragma GCC optimize(2)
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3624kb
input:
4 2 2 8101215 3 4 100000001000 2 2 80101215 3 4 1000000010000
output:
23 45 101 1000 Impossible Impossible
result:
ok 4 lines
Test #2:
score: -100
Wrong Answer
time: 35ms
memory: 5196kb
input:
1025 11 18 1461416814188088414188241035153540203545200202010354520510254921495628496328028281449632871435351535402035452002020103545205102500000000000000000000000000004000000063276372366381360363618638136918454921495628496328028281449632871435492149562849632802828144963287143514614168141880884141882...
output:
Impossible 3583 5 161650357972 65354104569 597523997017 7693 Impossible 406723924695110 973937089831524 59331138450754 554 4 189401911962950 980565699171 84748728972992 Impossible 62155650672 4241405 9458752764004792353 8717596993614 Impossible 941952596 49242258343771276739 Impossible 64053045751 4...
result:
wrong answer 119th lines differ - expected: '9 9691352', found: '3 27182739156'