QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#785704 | #9799. Magical Palette | Carucao# | TL | 40ms | 11156kb | C++20 | 4.0kb | 2024-11-26 18:52:02 | 2024-11-26 18:52:03 |
Judging History
answer
#include<bits/stdc++.h>
#define ls i<<1
#define rs i<<1|1
#define fi first
#define se second
#define min amin
#define max amax
#define eb emplace_back
using namespace std;
using ll=long long;
using LL=__int128;
using pii=pair<int,int>;
const int N=1E6+10;
const int inf=0x3f3f3f3f;
const int p=998244353;
template<typename T=int>T read(){T x;cin>>x;return x;}
template<typename U,typename V>U min(const U &x,const V &y){return x<y?x:y;}
template<typename U,typename V>U max(const U &x,const V &y){return y<x?x:y;}
template<typename U,typename ...V>U min(const U &x,const V &...y){return min(x,min(y...));}
template<typename U,typename ...V>U max(const U &x,const V &...y){return max(x,max(y...));}
template<typename U,typename V>bool cmin(U &x,const V &y){return y<x?x=y,true:false;}
template<typename U,typename V>bool cmax(U &x,const V &y){return x<y?x=y,true:false;}
template<typename U,typename ...V>bool cmin(U &x,const V &...y){return cmin(x,min(y...));}
template<typename U,typename ...V>bool cmax(U &x,const V &...y){return cmax(x,max(y...));}
template<typename U,typename V>U qpow(U x,V n){U y(1);for(;n;n>>=1,x*=x)if(n&1)y*=x;return y;}
ll sqrt_floor(const ll &x){ll l=0,r=inf;while(l+1^r){ll mid=l+r>>1;(x<mid*mid?r:l)=mid;}return l;}
ll sqrt_ceil(const ll &x){ll l=-1,r=inf;while(l+1^r){ll mid=l+r>>1;(mid*mid<x?l:r)=mid;}return r;}
istream &operator>>(istream &is,LL &x){string a;is>>a;bool k=a[0]=='-';if(k)a=a.substr(1);x=0;for(char &t:a)x=x*10+t-48;if(k)x=-x;return is;}
ostream &operator<<(ostream &os,LL x){if(x<0)os<<'-',x=-x;string a;do a+=x%10|48;while(x/=10);reverse(a.begin(),a.end());return os<<a;}
mt19937 rng(time(0));
struct mint{
int x;
mint():x(){}
mint(const int &x):x(x<0?x+p:x){}
mint inv()const{return qpow(*this,p-2);}
mint operator-()const{return mint(x?p-x:x);}
mint &operator+=(const mint &t){return (x+=t.x)<p?0:x-=p,*this;}
mint &operator-=(const mint &t){return (x-=t.x)<0?x+=p:0,*this;}
mint &operator*=(const mint &t){return x=ll(x)*t.x%p,*this;}
mint &operator/=(const mint &t){return *this*=t.inv();}
mint operator+(const mint &t)const{return mint(*this)+=t;}
mint operator-(const mint &t)const{return mint(*this)-=t;}
mint operator*(const mint &t)const{return mint(*this)*=t;}
mint operator/(const mint &t)const{return mint(*this)/=t;}
operator int()const{return x;}
bool operator==(const mint &t)const{return x==t.x;}
friend mint operator+(const mint &x,const int &y){return mint(x)+=y;}
friend mint operator-(const mint &x,const int &y){return mint(x)-=y;}
friend mint operator*(const mint &x,const int &y){return mint(x)*=y;}
friend mint operator/(const mint &x,const int &y){return mint(x)/=y;}
friend mint operator+(const int &x,const mint &y){return mint(x)+=y;}
friend mint operator-(const int &x,const mint &y){return mint(x)-=y;}
friend mint operator*(const int &x,const mint &y){return mint(x)*=y;}
friend mint operator/(const int &x,const mint &y){return mint(x)/=y;}
friend istream &operator>>(istream &is,mint &t){return is>>t.x;}
friend ostream &operator<<(ostream &os,const mint &t){return os<<t.x;}
};
int vis[N],tot;
void solve(){
int n,m;
cin>>n>>m;
int s=n*m;
vector<int>a(n),c(m);
for(int i=0,x=1%s;i<n;++i,(x+=m)%=s){
a[i]=x;
}
auto check=[&](int x)->bool{
++tot;
for(int t:a){
t=ll(t)*x%s;
if(vis[t]==tot)return false;
vis[t]=tot;
}
return true;
};
for(int i=0;i<m;++i){
int &x=c[i]=i;
while(x<s&&!check(x)){
x+=m;
}
if(x>=s){
cout<<"No\n";
return;
}
}
cout<<"Yes\n";
for(int &x:a){
cout<<x<<' ';
}
cout<<'\n';
for(int &x:c){
cout<<x<<' ';
}
cout<<'\n';
}
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
int T;
cin>>T;
while(T--){
solve();
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3688kb
input:
2 2 3 2 2
output:
Yes 1 4 3 1 5 No
result:
ok 2 cases (2 test cases)
Test #2:
score: 0
Accepted
time: 35ms
memory: 11080kb
input:
1 1 1000000
output:
Yes 1 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100...
result:
ok 1 cases (1 test case)
Test #3:
score: 0
Accepted
time: 40ms
memory: 11156kb
input:
1 1000000 1
output:
Yes 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 ...
result:
ok 1 cases (1 test case)
Test #4:
score: 0
Accepted
time: 1ms
memory: 5272kb
input:
1 2 500000
output:
No
result:
ok 1 cases (1 test case)
Test #5:
score: 0
Accepted
time: 26ms
memory: 9392kb
input:
1 2 499999
output:
Yes 1 500000 499999 1 500001 3 500003 5 500005 7 500007 9 500009 11 500011 13 500013 15 500015 17 500017 19 500019 21 500021 23 500023 25 500025 27 500027 29 500029 31 500031 33 500033 35 500035 37 500037 39 500039 41 500041 43 500043 45 500045 47 500047 49 500049 51 500051 53 500053 55 500055 57 5...
result:
ok 1 cases (1 test case)
Test #6:
score: -100
Time Limit Exceeded
input:
1 500000 2