QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#199535#6346. Record Parityucup-team870#WA 1ms3400kbC++141.7kb2023-10-04 12:53:272023-10-04 12:53:27

Judging History

你现在查看的是最新测评结果

  • [2023-10-04 12:53:27]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:3400kb
  • [2023-10-04 12:53:27]
  • 提交

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'