QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#449657#7979. 棋盘rqoi031100 ✓351ms1848kbC++142.8kb2024-06-21 15:41:322024-06-21 15:41:33

Judging History

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

  • [2024-06-21 15:41:33]
  • 评测
  • 测评结果:100
  • 用时:351ms
  • 内存:1848kb
  • [2024-06-21 15:41:32]
  • 提交

answer

#include<stdio.h>
#include<algorithm>
#include<cstring>
template<int N>
class number {
    private:
    int len,dig[N+5];
    public:
    constexpr number():len(0),dig{} {}
    constexpr number(int x):len(0),dig{} {
        while(x>0) {
            dig[len++]=x%10,x/=10;
        }
    }
    constexpr void clear() {
        std::memset(dig,0,len*sizeof(int));
    }
    constexpr void assign(int x) {
        clear();
        while(x>0) {
            dig[len++]=x%10,x/=10;
        }
    }
    constexpr void assign(const char* s) {
        clear();
        if(s[0]=='0') {
            return;
        }
        len=std::strlen(s);
        for(int i=0;i!=len;i++) {
            dig[i]=s[len-1-i]^'0';
        }
    }
    constexpr bool operator<(const number<N> &x) const {
        if(len!=x.len) {
            return len<x.len;
        }
        for(int i=len-1;i!=-1;i--) {
            if(dig[i]!=x.dig[i]) {
                return dig[i]<x.dig[i];
            }
        }
        return false;
    }
    constexpr number<N> operator+(const number<N> &x) const {
        number<N> y;
        y.len=std::max(len,x.len);
        for(int i=0;i!=y.len;i++) {
            if((y.dig[i]+=dig[i]+x.dig[i])>=10) {
                y.dig[i]-=10,++y.dig[i+1];
            }
        }
        y.len+=!!y.dig[y.len];
        return y;
    }
    constexpr number<N> &operator-=(const number<N> &x) {
        for(int i=0;i!=x.len;i++) {
            dig[i]-=x.dig[i];
            if(dig[i]<0) {
                dig[i]+=10,--dig[i+1];
            }
        }
        while(len>0&&!dig[len-1]) {
            --len;
        }
        return *this;
    }
    inline void print() const {
        if(len==0) {
            putchar('0');
            return;
        }
        for(int i=len-1;i!=-1;i--) {
            printf("%d",dig[i]);
        }
    }
};
number<100> fib[485];
char str[105],ans[965];
int main() {
    int k,q,x,y;
    scanf("%d%d%d%d",&k,&q,&x,&y);
    const int n(std::min(x>>1,480));
    fib[0].assign(1),fib[1].assign(1);
    int nx(1),ny(2);
    printf("%d\n",n<<1);
    printf("1 1\n1 2\n");
    for(int i=2;i<=n;i++) {
        fib[i]=fib[i-1]+fib[i-2];
        if(i&1) {
            ++ny;
            printf("%d %d\n",nx-1,ny);
        }
        else {
            ++nx;
            printf("%d %d\n",nx,ny-1);
        }
        printf("%d %d\n",nx,ny);
    }
    for(int i=1;i<=q;i++) {
        scanf("%s",str);
        number<100> tar;
        tar.assign(str);
        std::memset(ans,'0',n<<1);
        for(int j=n;j>=1;j--) {
            if(!(tar<fib[j])) {
                tar-=fib[j];
                ans[(j<<1)-1]='1';
            }
        }
        ans[n<<1]=0;
        puts(ans);
    }
    return 0;
}

详细

Subtask #1:

score: 5
Accepted

Test #1:

score: 5
Accepted
time: 0ms
memory: 1796kb

input:

3 999 1000 340
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
...

output:

960
1 1
1 2
2 1
2 2
1 3
2 3
3 2
3 3
2 4
3 4
4 3
4 4
3 5
4 5
5 4
5 5
4 6
5 6
6 5
6 6
5 7
6 7
7 6
7 7
6 8
7 8
8 7
8 8
7 9
8 9
9 8
9 9
8 10
9 10
10 9
10 10
9 11
10 11
11 10
11 11
10 12
11 12
12 11
12 12
11 13
12 13
13 12
13 13
12 14
13 14
14 13
14 14
13 15
14 15
15 14
15 15
14 16
15 16
16 15
16 16
15 1...

result:

ok correct

Subtask #2:

score: 10
Accepted

Test #2:

score: 10
Accepted
time: 7ms
memory: 1836kb

input:

12 10000 1000 340
358908473750
36343501002
904324605639
453955046266
725478753662
218319365131
882878650993
648345848966
474401697383
722377018680
718743783955
748051292505
167886140898
411111004914
327825244967
990026144963
623309580364
970889332700
319445927842
527624602835
453135227321
1153226125...

output:

960
1 1
1 2
2 1
2 2
1 3
2 3
3 2
3 3
2 4
3 4
4 3
4 4
3 5
4 5
5 4
5 5
4 6
5 6
6 5
6 6
5 7
6 7
7 6
7 7
6 8
7 8
8 7
8 8
7 9
8 9
9 8
9 9
8 10
9 10
10 9
10 10
9 11
10 11
11 10
11 11
10 12
11 12
12 11
12 12
11 13
12 13
13 12
13 13
12 14
13 14
14 13
14 14
13 15
14 15
15 14
15 15
14 16
15 16
16 15
16 16
15 1...

result:

ok correct

Test #3:

score: 0
Accepted
time: 8ms
memory: 1812kb

input:

12 10000 1000 340
930556110177
377904923573
36236934395
488122716493
51121341209
392176146788
323693311937
449196823461
336471392319
92713238333
281418059653
761936598942
293730650349
106748001462
609643804851
703543108800
999258707162
376689099489
435462123411
710775118008
45582546742
835557591196
...

output:

960
1 1
1 2
2 1
2 2
1 3
2 3
3 2
3 3
2 4
3 4
4 3
4 4
3 5
4 5
5 4
5 5
4 6
5 6
6 5
6 6
5 7
6 7
7 6
7 7
6 8
7 8
8 7
8 8
7 9
8 9
9 8
9 9
8 10
9 10
10 9
10 10
9 11
10 11
11 10
11 11
10 12
11 12
12 11
12 12
11 13
12 13
13 12
13 13
12 14
13 14
14 13
14 14
13 15
14 15
15 14
15 15
14 16
15 16
16 15
16 16
15 1...

result:

ok correct

Test #4:

score: 0
Accepted
time: 17ms
memory: 1784kb

input:

12 10000 1000 340
737930395319
182266797635
731674395027
268811900200
40636281734
385606961047
579973266668
244481758021
889308913416
116731076438
760018797175
690646649762
295657481984
860132997501
798927396859
973501342055
371555705903
89078273643
755892420101
664745115837
527923357928
12789900388...

output:

960
1 1
1 2
2 1
2 2
1 3
2 3
3 2
3 3
2 4
3 4
4 3
4 4
3 5
4 5
5 4
5 5
4 6
5 6
6 5
6 6
5 7
6 7
7 6
7 7
6 8
7 8
8 7
8 8
7 9
8 9
9 8
9 9
8 10
9 10
10 9
10 10
9 11
10 11
11 10
11 11
10 12
11 12
12 11
12 12
11 13
12 13
13 12
13 13
12 14
13 14
14 13
14 14
13 15
14 15
15 14
15 15
14 16
15 16
16 15
16 16
15 1...

result:

ok correct

Subtask #3:

score: 10
Accepted

Test #5:

score: 10
Accepted
time: 322ms
memory: 1840kb

input:

100 10000 1000 340
87490023455826213450979333037504606824522062808297739018786336978222089712660133428564103979384831
874900289913204769749000879539227331559680630241808944569515663934025397982898503777823815274323967
8749002899116133353924895735921513229471979456689635148877567298640178774668643967...

output:

960
1 1
1 2
2 1
2 2
1 3
2 3
3 2
3 3
2 4
3 4
4 3
4 4
3 5
4 5
5 4
5 5
4 6
5 6
6 5
6 6
5 7
6 7
7 6
7 7
6 8
7 8
8 7
8 8
7 9
8 9
9 8
9 9
8 10
9 10
10 9
10 10
9 11
10 11
11 10
11 11
10 12
11 12
12 11
12 12
11 13
12 13
13 12
13 13
12 14
13 14
14 13
14 14
13 15
14 15
15 14
15 15
14 16
15 16
16 15
16 16
15 1...

result:

ok correct

Test #6:

score: 0
Accepted
time: 334ms
memory: 1808kb

input:

100 10000 1000 340
8748936149282545611299720421204578485624739530690115026507467181657344327662766924981916612956258303
8714827106557313136171687656546075434718184787427526246530142735325290665843132579235229445895749631
8749002377650837755861570823748389228611868494396845969260163830921683752297192...

output:

960
1 1
1 2
2 1
2 2
1 3
2 3
3 2
3 3
2 4
3 4
4 3
4 4
3 5
4 5
5 4
5 5
4 6
5 6
6 5
6 6
5 7
6 7
7 6
7 7
6 8
7 8
8 7
8 8
7 9
8 9
9 8
9 9
8 10
9 10
10 9
10 10
9 11
10 11
11 10
11 11
10 12
11 12
12 11
12 12
11 13
12 13
13 12
13 13
12 14
13 14
14 13
14 14
13 15
14 15
15 14
15 15
14 16
15 16
16 15
16 16
15 1...

result:

ok correct

Subtask #4:

score: 10
Accepted

Test #7:

score: 10
Accepted
time: 351ms
memory: 1836kb

input:

100 10000 990 310
4083451712318559926139496762164571032902328806667934236880329773320213539959944736095945843081512968
7811890641057562314768022152641517082686481268288006737090208624016586608183953908313798353213188661
97358161226180890688421784730819518002666166790210320310558753031161862165361257...

output:

960
1 1
1 2
2 1
2 2
1 3
2 3
3 2
3 3
2 4
3 4
4 3
4 4
3 5
4 5
5 4
5 5
4 6
5 6
6 5
6 6
5 7
6 7
7 6
7 7
6 8
7 8
8 7
8 8
7 9
8 9
9 8
9 9
8 10
9 10
10 9
10 10
9 11
10 11
11 10
11 11
10 12
11 12
12 11
12 12
11 13
12 13
13 12
13 13
12 14
13 14
14 13
14 14
13 15
14 15
15 14
15 15
14 16
15 16
16 15
16 16
15 1...

result:

ok correct

Test #8:

score: 0
Accepted
time: 347ms
memory: 1788kb

input:

100 10000 990 310
536242740270410789572341652869398338093269589584059146826540461135298742334471009085914940446278287
4201975342869797382342066007535560618192359692007374881623572540610172361008282611340412383037024069
963134484370112575147508066354646119797740257454037562403391582920830075099761880...

output:

960
1 1
1 2
2 1
2 2
1 3
2 3
3 2
3 3
2 4
3 4
4 3
4 4
3 5
4 5
5 4
5 5
4 6
5 6
6 5
6 6
5 7
6 7
7 6
7 7
6 8
7 8
8 7
8 8
7 9
8 9
9 8
9 9
8 10
9 10
10 9
10 10
9 11
10 11
11 10
11 11
10 12
11 12
12 11
12 12
11 13
12 13
13 12
13 13
12 14
13 14
14 13
14 14
13 15
14 15
15 14
15 15
14 16
15 16
16 15
16 16
15 1...

result:

ok correct

Subtask #5:

score: 10
Accepted

Test #9:

score: 10
Accepted
time: 335ms
memory: 1788kb

input:

100 10000 1050 260
8749002899132047697490008908470485461412677723566863434996575047286849703722697797645542008396185599
8749002899132047697490008908470485461412677699052921091826559946707718798046219210886366418022957055
7655377536740541735303757766642121742076255665128332760334129720709510994307378...

output:

960
1 1
1 2
2 1
2 2
1 3
2 3
3 2
3 3
2 4
3 4
4 3
4 4
3 5
4 5
5 4
5 5
4 6
5 6
6 5
6 6
5 7
6 7
7 6
7 7
6 8
7 8
8 7
8 8
7 9
8 9
9 8
9 9
8 10
9 10
10 9
10 10
9 11
10 11
11 10
11 11
10 12
11 12
12 11
12 12
11 13
12 13
13 12
13 13
12 14
13 14
14 13
14 14
13 15
14 15
15 14
15 15
14 16
15 16
16 15
16 16
15 1...

result:

ok correct

Test #10:

score: 0
Accepted
time: 327ms
memory: 1796kb

input:

100 10000 1050 260
8749002899132047697490008908470485461412677723572849745703082425639811996797503692892926808185372671
874900289913204769701566661490981966686019183484759731181812123183820701469425350909196577361887231
87490028991280691115987306153332424033768113943575511927837611721527450026923859...

output:

960
1 1
1 2
2 1
2 2
1 3
2 3
3 2
3 3
2 4
3 4
4 3
4 4
3 5
4 5
5 4
5 5
4 6
5 6
6 5
6 6
5 7
6 7
7 6
7 7
6 8
7 8
8 7
8 8
7 9
8 9
9 8
9 9
8 10
9 10
10 9
10 10
9 11
10 11
11 10
11 11
10 12
11 12
12 11
12 12
11 13
12 13
13 12
13 13
12 14
13 14
14 13
14 14
13 15
14 15
15 14
15 15
14 16
15 16
16 15
16 16
15 1...

result:

ok correct

Subtask #6:

score: 10
Accepted

Test #11:

score: 10
Accepted
time: 335ms
memory: 1808kb

input:

100 10000 1050 240
8749002899132047697490008908470485461412677723572849734285100881333676956761384191490477496469520383
874886939179415873527191365288672777702448917037688119492655525651250910013304087281579324577152991
87490028991320476974900089084704854614126777235728490149522637601883528949454159...

output:

960
1 1
1 2
2 1
2 2
1 3
2 3
3 2
3 3
2 4
3 4
4 3
4 4
3 5
4 5
5 4
5 5
4 6
5 6
6 5
6 6
5 7
6 7
7 6
7 7
6 8
7 8
8 7
8 8
7 9
8 9
9 8
9 9
8 10
9 10
10 9
10 10
9 11
10 11
11 10
11 11
10 12
11 12
12 11
12 12
11 13
12 13
13 12
13 13
12 14
13 14
14 13
14 14
13 15
14 15
15 14
15 15
14 16
15 16
16 15
16 16
15 1...

result:

ok correct

Test #12:

score: 0
Accepted
time: 323ms
memory: 1836kb

input:

100 10000 1050 240
8748869399942302640609859219613849864404711585518072959767189754493152526763381301362784876544131071
8749002898113529709322765865336262617207988643047115548870114300321741770881768540817196765514039295
8749002899132047697490008908470485448242213512826165447361161116479336307579296...

output:

960
1 1
1 2
2 1
2 2
1 3
2 3
3 2
3 3
2 4
3 4
4 3
4 4
3 5
4 5
5 4
5 5
4 6
5 6
6 5
6 6
5 7
6 7
7 6
7 7
6 8
7 8
8 7
8 8
7 9
8 9
9 8
9 9
8 10
9 10
10 9
10 10
9 11
10 11
11 10
11 11
10 12
11 12
12 11
12 12
11 13
12 13
13 12
13 13
12 14
13 14
14 13
14 14
13 15
14 15
15 14
15 15
14 16
15 16
16 15
16 16
15 1...

result:

ok correct

Subtask #7:

score: 20
Accepted

Test #13:

score: 20
Accepted
time: 0ms
memory: 1780kb

input:

100 1 980 260
8749002899132047697490008908470485461309833682610292204604841418296589481615503153703163411103219711

output:

960
1 1
1 2
2 1
2 2
1 3
2 3
3 2
3 3
2 4
3 4
4 3
4 4
3 5
4 5
5 4
5 5
4 6
5 6
6 5
6 6
5 7
6 7
7 6
7 7
6 8
7 8
8 7
8 8
7 9
8 9
9 8
9 9
8 10
9 10
10 9
10 10
9 11
10 11
11 10
11 11
10 12
11 12
12 11
12 12
11 13
12 13
13 12
13 13
12 14
13 14
14 13
14 14
13 15
14 15
15 14
15 15
14 16
15 16
16 15
16 16
15 1...

result:

ok correct

Test #14:

score: 0
Accepted
time: 0ms
memory: 1840kb

input:

100 1 980 260
26140399507039494187363454808469075954177491358550589658445256177636481188801043146566104810349008

output:

960
1 1
1 2
2 1
2 2
1 3
2 3
3 2
3 3
2 4
3 4
4 3
4 4
3 5
4 5
5 4
5 5
4 6
5 6
6 5
6 6
5 7
6 7
7 6
7 7
6 8
7 8
8 7
8 8
7 9
8 9
9 8
9 9
8 10
9 10
10 9
10 10
9 11
10 11
11 10
11 11
10 12
11 12
12 11
12 12
11 13
12 13
13 12
13 13
12 14
13 14
14 13
14 14
13 15
14 15
15 14
15 15
14 16
15 16
16 15
16 16
15 1...

result:

ok correct

Test #15:

score: 0
Accepted
time: 0ms
memory: 1848kb

input:

100 1 980 260
2916334299201423571746379638671656065302994540964775389402649871877310689655011516150737480170427669

output:

960
1 1
1 2
2 1
2 2
1 3
2 3
3 2
3 3
2 4
3 4
4 3
4 4
3 5
4 5
5 4
5 5
4 6
5 6
6 5
6 6
5 7
6 7
7 6
7 7
6 8
7 8
8 7
8 8
7 9
8 9
9 8
9 9
8 10
9 10
10 9
10 10
9 11
10 11
11 10
11 11
10 12
11 12
12 11
12 12
11 13
12 13
13 12
13 13
12 14
13 14
14 13
14 14
13 15
14 15
15 14
15 15
14 16
15 16
16 15
16 16
15 1...

result:

ok correct

Test #16:

score: 0
Accepted
time: 0ms
memory: 1780kb

input:

100 1 980 260
133733063818254349335501779590031438654517135520213587361323145147457390997763303065570586431533875

output:

960
1 1
1 2
2 1
2 2
1 3
2 3
3 2
3 3
2 4
3 4
4 3
4 4
3 5
4 5
5 4
5 5
4 6
5 6
6 5
6 6
5 7
6 7
7 6
7 7
6 8
7 8
8 7
8 8
7 9
8 9
9 8
9 9
8 10
9 10
10 9
10 10
9 11
10 11
11 10
11 11
10 12
11 12
12 11
12 12
11 13
12 13
13 12
13 13
12 14
13 14
14 13
14 14
13 15
14 15
15 14
15 15
14 16
15 16
16 15
16 16
15 1...

result:

ok correct

Test #17:

score: 0
Accepted
time: 0ms
memory: 1808kb

input:

100 1 980 260
9216845717656874712980450562726202415567360565980794777111390850331644813674856981646960226192287360

output:

960
1 1
1 2
2 1
2 2
1 3
2 3
3 2
3 3
2 4
3 4
4 3
4 4
3 5
4 5
5 4
5 5
4 6
5 6
6 5
6 6
5 7
6 7
7 6
7 7
6 8
7 8
8 7
8 8
7 9
8 9
9 8
9 9
8 10
9 10
10 9
10 10
9 11
10 11
11 10
11 11
10 12
11 12
12 11
12 12
11 13
12 13
13 12
13 13
12 14
13 14
14 13
14 14
13 15
14 15
15 14
15 15
14 16
15 16
16 15
16 16
15 1...

result:

ok correct

Test #18:

score: 0
Accepted
time: 0ms
memory: 1840kb

input:

100 1 980 260
5264952002436106359851318041422054633517706683530105573021775026464088057584242164048188378737906836

output:

960
1 1
1 2
2 1
2 2
1 3
2 3
3 2
3 3
2 4
3 4
4 3
4 4
3 5
4 5
5 4
5 5
4 6
5 6
6 5
6 6
5 7
6 7
7 6
7 7
6 8
7 8
8 7
8 8
7 9
8 9
9 8
9 9
8 10
9 10
10 9
10 10
9 11
10 11
11 10
11 11
10 12
11 12
12 11
12 12
11 13
12 13
13 12
13 13
12 14
13 14
14 13
14 14
13 15
14 15
15 14
15 15
14 16
15 16
16 15
16 16
15 1...

result:

ok correct

Subtask #8:

score: 25
Accepted

Test #19:

score: 25
Accepted
time: 334ms
memory: 1736kb

input:

100 10000 960 240
8749002899132047697015724510954438324957730968977252383122989921226002617013223698533483281626692607
8749002899132047697490008908470485461412677720507858663971304708923117942496885325656574463725010943
87148271065573131361716885470369961093519598137825155235803895087505468828694702...

output:

960
1 1
1 2
2 1
2 2
1 3
2 3
3 2
3 3
2 4
3 4
4 3
4 4
3 5
4 5
5 4
5 5
4 6
5 6
6 5
6 6
5 7
6 7
7 6
7 7
6 8
7 8
8 7
8 8
7 9
8 9
9 8
9 9
8 10
9 10
10 9
10 10
9 11
10 11
11 10
11 11
10 12
11 12
12 11
12 12
11 13
12 13
13 12
13 13
12 14
13 14
14 13
14 14
13 15
14 15
15 14
15 15
14 16
15 16
16 15
16 16
15 1...

result:

ok correct

Test #20:

score: 0
Accepted
time: 330ms
memory: 1736kb

input:

100 10000 960 240
87490028991320476974751875210481089883984606374917376934978638676026103357677379577201035900354559
874900289913204769748997996044817613236382183082659757372611910814364558665649382849850729809805311
87490028979301854287209922417527640508689863212316623120229713820718860216280007473...

output:

960
1 1
1 2
2 1
2 2
1 3
2 3
3 2
3 3
2 4
3 4
4 3
4 4
3 5
4 5
5 4
5 5
4 6
5 6
6 5
6 6
5 7
6 7
7 6
7 7
6 8
7 8
8 7
8 8
7 9
8 9
9 8
9 9
8 10
9 10
10 9
10 10
9 11
10 11
11 10
11 11
10 12
11 12
12 11
12 12
11 13
12 13
13 12
13 13
12 14
13 14
14 13
14 14
13 15
14 15
15 14
15 15
14 16
15 16
16 15
16 16
15 1...

result:

ok correct