QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#785691 | #9799. Magical Palette | Carucao# | RE | 39ms | 11116kb | C++20 | 4.0kb | 2024-11-26 18:49:38 | 2024-11-26 18:49:42 |
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*=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;
}
詳細信息
Test #1:
score: 100
Accepted
time: 0ms
memory: 3732kb
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: 33ms
memory: 11060kb
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: 39ms
memory: 11116kb
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: -100
Runtime Error
input:
1 2 500000