QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#449657 | #7979. 棋盘 | rqoi031 | 100 ✓ | 351ms | 1848kb | C++14 | 2.8kb | 2024-06-21 15:41:32 | 2024-06-21 15:41:33 |
Judging History
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