QOJ.ac
QOJ
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #848112 | #9988. 挑战大模型 | Lehe | WA | 619ms | 6856kb | C++23 | 2.0kb | 2025-01-08 15:49:20 | 2025-01-08 15:49:22 |
Judging History
answer
#include<bits/stdc++.h>
#define ll long long
using namespace std;
int n,m,t1[505][505],t2[505][505];
int g[505][505];
int s1[505],s2[505];
void init()
{
for(int i = 1;i <= n;i++)
s1[i] = 1;
for(int i = 1;i <= m;i++)
s2[i] = 1;
for(int i = 1;i <= n;i++)
for(int j = 1;j <= m;j++)
if(t1[i][j] != t2[i][j])
s1[i] = 0,s2[j] = 0;
for(int i = 1;i <= n;i++)
s1[i] += s1[i - 1];
for(int i = 1;i <= m;i++)
s2[i] += s2[i - 1];
}
bool check1(int l,int r)
{
if(l > r)
return 1;
return s1[r] - s1[l - 1] == r - l + 1;
}
bool check2(int l,int r)
{
if(l > r)
return 1;
return s2[r] - s2[l - 1] == r - l + 1;
}
int d[505],q[505],ql,qr,cl;
void insert(int p,int v)
{
while(ql <= qr && q[qr] > v)
qr--;
qr++,d[qr] = p,q[qr] = v;
}
int getmin()
{
while(ql <= qr && d[ql] < cl)
ql++;
if(ql > qr)
return 0;
return q[ql];
}
int main()
{
//freopen("data.in","r",stdin);
//freopen("data.out","w",stdout);
scanf("%d%d",&n,&m);
for(int i = 1;i <= n;i++)
for(int j = 1;j <= m;j++)
scanf("%1d",&t1[i][j]);
for(int i = 1;i <= n;i++)
for(int j = 1;j <= m;j++)
scanf("%1d",&t2[i][j]);
init();
for(int len = 1;len < m;len++)
{
memset(g,0,sizeof g);
for(int i = 1;i <= n;i++)
for(int j = len + 1;j <= m;j++)
g[i][j] = (t1[i][j] == t2[i][j - len] ? g[i][j - 1] + 1 : 0);
int ans = 0;
for(int j = len + 1;j <= m;j++)
{
if(!check2(j + 1,m))
continue;
memset(d,0,sizeof d);
memset(q,0,sizeof q);
ql = 1,qr = 0,cl = 1;
for(int cr = 1;cr <= n;cr++)
{
insert(cr,g[cr][j]);
while(cl <= cr && (!check2(1,j - len - getmin()) || !check2(j - len + 1,j - getmin())))
cl++;
if(cl > cr)
continue;
int tmp = getmin();
if(check2(1,j - len - tmp) && check2(j - len + 1,j - tmp) && check1(1,cl - 1) && check1(cr + 1,n))
{
ans = max(ans,tmp * (cr - cl + 1));
}
}
}
printf("%d%c",ans == 0 ? -1 : ans," \n"[len == m - 1]);
}
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 510ms
memory: 6700kb
input:
484 484 1001110011010001101100110111010110011011110110101001010000101111010111001100111011010010000011110111011101000101000011011011100111001111111100100101101000111000100000011100110011101000101000010100101010011110000111101101100110000110111100100001111001110111010001000111101001111111001000001001...
output:
-1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 ...
result:
ok 483 numbers
Test #2:
score: 0
Accepted
time: 619ms
memory: 6840kb
input:
484 484 0111111010101000011110010000001010001100101001010101100001011110110001011111100110111111010100111010111011101010001100101101110111101000100001100000110000000011000100100100011001010110110101101110100010010100001010110100110001001000101101100011000011000011111001011001110111111100001110001111...
output:
-1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 9156 -1 -1 -1 -1 -1 -...
result:
ok 483 numbers
Test #3:
score: 0
Accepted
time: 512ms
memory: 6816kb
input:
486 486 1101001010110010100000111110001110010111110111000010001111111100101110011000101100100100011100110000001001000110111001000111100001001100010001100000100111011111010100101110100100010001010101100110111100110110111111010110000110101011001010001110100111011000000100110010000110100101000101111001...
output:
-1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 4437 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -...
result:
ok 485 numbers
Test #4:
score: 0
Accepted
time: 430ms
memory: 6856kb
input:
491 491 1110110101101001101110001001100111111101011110000111101101010001010100000011010001101011011001101011010011011011101110010110100001110110111011111100101100111111000100111011100110110100101010001011000001101111100110010110010101001001111000111110011001000010111011001111001100101101010011111010...
output:
-1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 16940 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 ...
result:
ok 490 numbers
Test #5:
score: 0
Accepted
time: 273ms
memory: 6780kb
input:
481 481 0000000000001000000100000000010010000001110000000000000001010000001000000000000100000001001000000000000000000000000000000000000001000000000000001000000000000000000000011000001000001000000000000000000100000000000000110000000010010000000000000000000000001000010000100000000000000000000000001100...
output:
-1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 880...
result:
ok 480 numbers
Test #6:
score: 0
Accepted
time: 340ms
memory: 6836kb
input:
499 499 0100010001010000000010000000000001000000000000000000000000000000000110000000000000000000000000000000000000000010001000000000010000000000000000000000000000000000000000000000000000001000000000000000000000000000100100000000000100001000000000000000001000001100000000000000000000000000000010001010...
output:
-1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 16440 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 ...
result:
ok 498 numbers
Test #7:
score: 0
Accepted
time: 508ms
memory: 6704kb
input:
487 487 0101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101010101...
output:
-1 236195 -1 235221 -1 234247 -1 233273 -1 232299 -1 231325 -1 230351 -1 229377 -1 228403 -1 227429 -1 226455 -1 225481 -1 224507 -1 223533 -1 222559 -1 221585 -1 220611 -1 219637 -1 218663 -1 217689 -1 216715 -1 215741 -1 214767 -1 213793 -1 212819 -1 211845 -1 210871 -1 209897 -1 208923 -1 207949 ...
result:
ok 486 numbers
Test #8:
score: 0
Accepted
time: 514ms
memory: 6728kb
input:
491 491 1001000011010011000100110001001110001000110010000011110000101111100000010000010101000100110100000100100100000110110000000010101011110110001000100001011001101001011000000011101110000010010001100000000100001000000000100000001001001110001010110000011001110000000100000010001100011111100011010110...
output:
-1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 544...
result:
ok 490 numbers
Test #9:
score: 0
Accepted
time: 468ms
memory: 6788kb
input:
488 488 1110100001001100011000110100010010110011000001110101001010101011110000001010000101101011110100000101010001100001010000000111001100010100101010100001011101010001111010101111110011100101111000000001100110111001100001000011001110111011011011010100111000111100000001111101111110010010110011101010...
output:
-1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 ...
result:
ok 487 numbers
Test #10:
score: 0
Accepted
time: 1ms
memory: 6260kb
input:
20 20 10001100100101101001 11000010110010000111 11010111110000100001 11011011100010111000 10111001001011111001 11101101101110000011 10101011000111000010 01111110011110110100 10001000000011000100 01101111010110100100 10001010010010001101 00010100000010001101 11101000101001100100 00011110001110100000 ...
output:
4 -1 3 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1
result:
ok 19 numbers
Test #11:
score: 0
Accepted
time: 302ms
memory: 6776kb
input:
492 492 1101000011111110001000010100011010001110100101110101001000111101111111000001001101100111011000100100101111100000001101111110011111010110101010101100100000110010001101000000101110011100110000010011001010111011100001101100010100011001111101000110101000110101010101101000010010101110111010110011...
output:
-1 225624 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1...
result:
ok 491 numbers
Test #12:
score: 0
Accepted
time: 413ms
memory: 6856kb
input:
497 497 0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000001111001010010001111101111110111111111011101111111111111110111011111011111110111111111101111111110110101...
output:
-1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 10812 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 ...
result:
ok 496 numbers
Test #13:
score: 0
Accepted
time: 406ms
memory: 6684kb
input:
489 489 0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000...
output:
-1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 51345 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 ...
result:
ok 488 numbers
Test #14:
score: 0
Accepted
time: 1ms
memory: 6464kb
input:
7 15 001010011101000 110001111110110 010101100011111 100000100011010 110100100101000 110011011010101 010001011011111 010011101000110 001111110110010 101100011111001 000100011010010 100100101001110 110011011010101 010001011011111
output:
-1 -1 55 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1
result:
ok 14 numbers
Test #15:
score: 0
Accepted
time: 25ms
memory: 6240kb
input:
10 500 10001110001110011101010001101010000111110101101111000100011110110101000010000110000110111000111101101110011000000011010110101001010101000110110000101000011001100110011000001101110010001101011011110001001111100100110000011110000100000100010001010010011011011000000110111101000010111010100100111...
output:
-1 -1 5 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 4 -1 5 -1 -1 4 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 5 5 4 4 -1 -1 -1 -1 -1 -1 -1 4 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 4 -1 -1 -1 -1 -1 -1 -1 4 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 5 -1 -1 -1 -1 -1 -1 -1 12 ...
result:
ok 499 numbers
Test #16:
score: 0
Accepted
time: 162ms
memory: 6408kb
input:
100 500 0000001101101100110110110010110110010110000010001001010001010010011000111110011111000100010111100000111010011101011101100110000010100001100000101011010001010011101111001001000001100111110101010101001101101100000111001011110100000100110001001110011110010000011001010100000110101011100100111010...
output:
-1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 8 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -...
result:
ok 499 numbers
Test #17:
score: -100
Wrong Answer
time: 36ms
memory: 4868kb
input:
20 500 11010110010011101110111111001100001011110111001001010101001101101111000010100000101010110110001010110111101011001000000011111011000000110111000000000001111110011011010100000000110110110001001100011101100110101111100100110000011001110101011100011011000001100000001011110010011100100110001001001...
output:
2 -1 -1 -1 3 -1 5 6 6 3 -1 -1 -1 6 -1 -1 -1 3 8 6 -1 2 -1 -1 -1 -1 6 4 -1 4 -1 -1 -1 2 -1 -1 4 -1 -1 6 -1 -1 6 4 -1 -1 4 -1 6 8 3 -1 5 5 6 4 -1 6 -1 -1 8 9 -1 -1 2 -1 3 7 6 -1 -1 -1 -1 -1 -1 4 -1 -1 4 -1 -1 8 -1 -1 4 -1 6 7 -1 -1 -1 2 -1 -1 -1 -1 3 -1 -1 6 -1 6 -1 5 -1 -1 -1 -1 2 -1 -1 -1 -1 2 -1 10...
result:
wrong answer 5th numbers differ - expected: '4', found: '3'