QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#199535 | #6346. Record Parity | ucup-team870# | WA | 1ms | 3400kb | C++14 | 1.7kb | 2023-10-04 12:53:27 | 2023-10-04 12:53:27 |
Judging History
answer
#include <bits/stdc++.h>
#define rep(i,l,r) for(int i=l; i<=r; i++)
#define per(i,r,l) for(int i=r; i>=l; i--)
#define IOS {cin.tie(0);cout.tie(0);ios::sync_with_stdio(0);}
using namespace std;
typedef long long ll;
typedef pair<int,int> P;
int V,X,Y;
void exgcd(int a,int b){
if(b==0){
X=1; Y=0; return;
}
exgcd(b,a%b);
int tx=X; X=Y; Y=tx-a/b*Y;
}
int cal(int x,int y){
exgcd(x,y);
int a=X,b=Y;
b=((1ll*b*V%x)+x)%x;
if(b==0)b=x;
ll v=(V-1ll*b*y)/x-1; assert((V-1ll*b*y)%x==0);
if(v<0)return 0;
return v/y+1;
}
void slv(){
vector<P>ans;
int n,k; cin>>n>>k; V=n+2;
int x=1,y=1;
if(cal(x,y)<k){
cout<<"-1\n";return;
}
while(1){
// cout<<x<<' '<<y<<'\n';
int L=0,R=(V-y)/x;
while(L<=R){
int mid=(L+R)>>1;
if(cal(x,mid*x+y)>=k)L=mid+1;
else R=mid-1;
}
--L;
if(L)ans.push_back({0,L});
y+=x*L;
cout<<L<<' '<<x<<' '<<y<<'\n';
if(x+y==V)break;
k-=cal(x,x+y);
x+=y;
ans.push_back({1,1});
if(x+y==V)break;
}
vector<P>res;
int pre=-1,num=0;
for(auto [s,cnt]:ans){
if(s!=pre){
if(pre!=-1)res.push_back({pre,num});
pre=s; num=cnt;
}
else num+=cnt;
}
res.push_back({pre,num});
cout<<res.size()<<' '<<res[0].first<<'\n';
for(auto [_,v]:res)cout<<v<<' '; cout<<'\n';
}
int main() {
// IOS
int T;cin>>T;
while(T--)slv();
}
/*
100
99824 4353
21 1 22
13 23 321
5 344 2041
40 2385 97441
7 0
21 1 13 1 5 1 40
8
99824 4353
2129721 207087
3 1
3 2
3 3
3 4
3 5
1000000000 1
*/
详细
Test #1:
score: 0
Wrong Answer
time: 1ms
memory: 3400kb
input:
5 2 4 1 2 5 3
output:
-1 0 1 1 1 1 1 1 1 2 0 3 2 2 0 1 2 5 1 6 1 0 5 5 1 6 1 0 5
result:
wrong answer 1st numbers differ - expected: '3', found: '-1'