QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#355634 | #5107. Mosaic Browsing | InfinityNS# | WA | 1109ms | 223112kb | C++14 | 5.2kb | 2024-03-17 00:31:12 | 2024-03-17 00:31:13 |
Judging History
answer
#include<bits/stdc++.h>
#define ff first
#define pb push_back
#define ss second
#define ld long double
#define ll long long
using namespace std;
typedef pair<int,int> pii;
using cd=complex<long double>;
namespace polynomial{
const ld PI=acos(-1);
const int maxn=(1<<22);
cd prekw[maxn];
bool isprek=0;
void prek(){
if(isprek)return;
isprek=1;
for(int i=0;i<maxn;i++){
ld angle=(2*PI)/maxn*i;
prekw[i]=cd(cos(angle),sin(angle));
}
}
void fft(vector<cd>&a,bool invert){
int n=a.size();
prek();
int j=0;
for(int i=1;i<n;i++){
int bit=n>>1;
for(;j&bit;bit>>=1)j^=bit;
j^=bit;
if(i<j)swap(a[i],a[j]);
}
for(int len=2;len<=n;len<<=1){
int hlen=len>>1;
for(int i=0;i<n;i+=len){
int curr=0;
int d=maxn/len;
if(invert)d=maxn-d;
for(int j=0;j<hlen;j++){
cd pom1=a[i+j];
cd pom2=prekw[curr]*a[i+j+hlen];
a[i+j]=pom1+pom2;
a[i+j+hlen]=pom1-pom2;
curr+=d;
if(curr>=maxn)curr-=maxn;
}
}
}
}
cd operator /(cd a,ld n){
return cd(a.real()/n,a.imag()/n);
}
struct polyn{
vector<ll>a;
int size(){return a.size();}
void resize(int x){a.resize(x);}
ll& operator [](int x){
if(x>=a.size())a.resize(x+1);
return a[x];
}
polyn operator +(polyn b){
polyn ret=(*this);
for(int i=0;i<b.size();i++)ret[i]+=b[i];
return ret;
}
polyn operator -(polyn b){
polyn ret=(*this);
for(int i=0;i<b.size();i++)ret[i]-=b[i];
return ret;
}
polyn operator *(polyn b){
int n=1;
while(n<size()+b.size()-1)n<<=1;
vector<cd>fa(n),fb(n);
for(int i=0;i<a.size();i++)fa[i].real(a[i]);
for(int i=0;i<b.size();i++)fb[i].real(b[i]);
fft(fa,0);
fft(fb,0);
for(int i=0;i<n;i++)fa[i]=(fa[i]*fb[i])/n;
fft(fa,1);
polyn ret;
ret.resize(n);
for(int i=0;i<n;i++){
ret[i]=round(fa[i].real());
}
return ret;
}
void ispis(){
for(int i=0;i<a.size();i++){
printf("%lld ",a[i]);
}
printf("\n");
}
};
}
using namespace polynomial;
const int mpn=1010;
int a[mpn][mpn],b[mpn][mpn],c[mpn][mpn];
int r1,r2,c1,c2;
polyn matchuj(polyn a,polyn b){
//a.ispis();
//b.ispis();
reverse(b.a.begin(),b.a.end());
polyn b3;
polyn ones;
for(int i=0;i<b.size();i++){
b3[i]=b[i]*b[i]*b[i];
ones[i]=1;
}
polyn a2;
for(int i=0;i<a.size();i++){
a2[i]=a[i]*a[i];
}
polyn b2;
for(int i=0;i<b.size();i++){
b2[i]=-2*b[i]*b[i];
}
//printf("POSL\n");
//(b*a2).ispis();
//(a*b2).ispis();
//(b3*ones).ispis();
return b*a2+a*b2+b3*ones;
}
int main(){
///freopen("test.txt","r",stdin);
/*polyn a,b;
a.a.pb(1);
a.a.pb(1);
b.a.pb(2);
b.a.pb(3);
b.a.pb(5);
a=a*b;
a.ispis();*/
scanf("%d %d",&r1,&c1);
int mnr=r1;
int mnc=c1;
for(int i=0;i<r1;i++){
for(int j=0;j<c1;j++){
scanf("%d",&a[i][j]);
if(a[i][j]){
mnr=min(mnr,i);
mnc=min(mnc,j);
}
}
}
for(int i=mnr;i<r1;i++){
for(int j=mnc;j<c1;j++){
c[i-mnr][j-mnc]=a[i][j];
}
}
int mxr=0;
int mxc=0;
for(int i=0;i<r1;i++){
for(int j=0;j<c1;j++){
if(c[i][j]){
mxr=max(mxr,i);
mxc=max(mxc,j);
}
}
}
r1=mxr+1;
c1=mxc+1;
scanf("%d %d",&r2,&c2);
for(int i=0;i<r2;i++){
for(int j=0;j<c2;j++){
scanf("%d",&b[i][j]);
}
}
if(r1>r2 || c1>c2){
printf("0\n");
return 0;
}
polyn bp,cp;
for(int i=0;i<r2;i++){
for(int j=0;j<c2;j++){
bp.a.pb(b[i][j]);
cp.a.pb(c[i][j]);
//printf("%d ",c[i][j]);
}
//printf("\n");
}
polyn pom=matchuj(bp,cp);
///pom.ispis();
vector<pii>rez;
int curr=-1;
int n=r2*c2;
for(int i=0;i<r2;i++){
for(int j=0;j<c2;j++){
curr++;
//printf("%d %d | %d %d AA\n",i,j,i+r1-1,j+c1-1);
if(i+r1-1>=r2 || j+c1-1>=c2)continue;
if(pom[curr+n-1]==0)rez.pb({i,j});
}
}
sort(rez.begin(),rez.end());
printf("%d\n",rez.size());
for(int i=0;i<rez.size();i++){
printf("%d %d\n",rez[i].ff+1,rez[i].ss+1);
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 1103ms
memory: 217708kb
input:
100 100 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 99 100 ...
output:
2005 1 1 1 101 1 201 1 301 1 401 2 1 2 101 2 201 2 301 2 401 3 1 3 101 3 201 3 301 3 401 4 1 4 101 4 201 4 301 4 401 5 1 5 101 5 201 5 301 5 401 6 1 6 101 6 201 6 301 6 401 7 1 7 101 7 201 7 301 7 401 8 1 8 101 8 201 8 301 8 401 9 1 9 101 9 201 9 301 9 401 10 1 10 101 10 201 10 301 10 401 11 1 11 10...
result:
ok 2006 lines
Test #2:
score: 0
Accepted
time: 1109ms
memory: 218288kb
input:
250 100 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 99 100 ...
output:
1255 1 1 1 101 1 201 1 301 1 401 2 1 2 101 2 201 2 301 2 401 3 1 3 101 3 201 3 301 3 401 4 1 4 101 4 201 4 301 4 401 5 1 5 101 5 201 5 301 5 401 6 1 6 101 6 201 6 301 6 401 7 1 7 101 7 201 7 301 7 401 8 1 8 101 8 201 8 301 8 401 9 1 9 101 9 201 9 301 9 401 10 1 10 101 10 201 10 301 10 401 11 1 11 10...
result:
ok 1256 lines
Test #3:
score: 0
Accepted
time: 1088ms
memory: 223112kb
input:
500 100 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 99 100 ...
output:
5 1 1 1 101 1 201 1 301 1 401
result:
ok 6 lines
Test #4:
score: 0
Accepted
time: 200ms
memory: 139268kb
input:
1 1 1 3 3 1 1 1 1 1 1 1 1 1
output:
9 1 1 1 2 1 3 2 1 2 2 2 3 3 1 3 2 3 3
result:
ok 10 lines
Test #5:
score: 0
Accepted
time: 188ms
memory: 138980kb
input:
1 1 2 2 4 1 1 2 2 1 3 2 3
output:
3 1 3 1 4 2 3
result:
ok 4 lines
Test #6:
score: 0
Accepted
time: 191ms
memory: 138948kb
input:
1 1 1 4 1 1 4 2 6
output:
1 1 1
result:
ok 2 lines
Test #7:
score: 0
Accepted
time: 180ms
memory: 138956kb
input:
1 1 1 3 3 1 1 1 1 1 1 1 1 1
output:
9 1 1 1 2 1 3 2 1 2 2 2 3 3 1 3 2 3 3
result:
ok 10 lines
Test #8:
score: 0
Accepted
time: 194ms
memory: 138988kb
input:
2 2 1 3 0 0 1 3 1 2 3
output:
0
result:
ok single line: '0'
Test #9:
score: 0
Accepted
time: 1ms
memory: 7860kb
input:
1 4 4 4 4 1 1 1 2
output:
0
result:
ok single line: '0'
Test #10:
score: 0
Accepted
time: 192ms
memory: 138992kb
input:
1 1 0 6 4 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
output:
24 1 1 1 2 1 3 1 4 2 1 2 2 2 3 2 4 3 1 3 2 3 3 3 4 4 1 4 2 4 3 4 4 5 1 5 2 5 3 5 4 6 1 6 2 6 3 6 4
result:
ok 25 lines
Test #11:
score: 0
Accepted
time: 188ms
memory: 138952kb
input:
1 1 2 1 5 3 2 3 3 2
output:
2 1 2 1 5
result:
ok 3 lines
Test #12:
score: 0
Accepted
time: 200ms
memory: 138924kb
input:
1 1 3 2 8 7 2 6 3 7 2 5 3 1 5 3 4 1 3 3 6
output:
5 1 4 1 8 2 3 2 6 2 7
result:
ok 6 lines
Test #13:
score: 0
Accepted
time: 0ms
memory: 7784kb
input:
2 3 1 1 0 1 1 0 1 7 1 1 1 1 1 1 1
output:
0
result:
ok single line: '0'
Test #14:
score: 0
Accepted
time: 174ms
memory: 139268kb
input:
2 2 0 1 2 2 9 3 2 3 2 1 1 1 1 3 2 1 1 1 1 2 2 3 3 3 1 1 3 1 3 3 1 3 1
output:
1 4 2
result:
ok 2 lines
Test #15:
score: 0
Accepted
time: 192ms
memory: 139264kb
input:
1 1 2 4 3 5 6 5 3 2 4 1 2 4 7 3 5
output:
2 2 2 3 2
result:
ok 3 lines
Test #16:
score: 0
Accepted
time: 0ms
memory: 7832kb
input:
5 4 1 0 1 1 0 0 1 0 1 0 0 1 1 0 0 0 0 0 1 1 3 1 1 1 1
output:
0
result:
ok single line: '0'
Test #17:
score: 0
Accepted
time: 1ms
memory: 7912kb
input:
4 2 3 0 0 0 1 2 3 2 1 4 1 1 1 2
output:
0
result:
ok single line: '0'
Test #18:
score: 0
Accepted
time: 1ms
memory: 7876kb
input:
8 8 0 2 3 6 5 3 5 2 6 5 6 5 3 2 0 5 2 1 5 3 0 0 4 2 2 0 7 2 3 5 3 7 5 1 4 6 0 5 6 7 3 0 1 0 5 4 5 7 3 4 6 1 5 3 3 1 3 6 7 3 6 1 5 5 4 4 7 7 3 7 2 4 5 3 6 3 1 1 3 7 2 1
output:
0
result:
ok single line: '0'
Test #19:
score: 0
Accepted
time: 192ms
memory: 138972kb
input:
1 1 61 4 1 52 48 40 46
output:
0
result:
ok single line: '0'
Test #20:
score: 0
Accepted
time: 225ms
memory: 140824kb
input:
1 1 1 95 86 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ...
output:
8170 1 1 1 2 1 3 1 4 1 5 1 6 1 7 1 8 1 9 1 10 1 11 1 12 1 13 1 14 1 15 1 16 1 17 1 18 1 19 1 20 1 21 1 22 1 23 1 24 1 25 1 26 1 27 1 28 1 29 1 30 1 31 1 32 1 33 1 34 1 35 1 36 1 37 1 38 1 39 1 40 1 41 1 42 1 43 1 44 1 45 1 46 1 47 1 48 1 49 1 50 1 51 1 52 1 53 1 54 1 55 1 56 1 57 1 58 1 59 1 60 1 61...
result:
ok 8171 lines
Test #21:
score: 0
Accepted
time: 161ms
memory: 139132kb
input:
1 1 2 6 96 3 2 1 2 1 1 3 2 1 2 2 3 1 3 3 3 3 2 2 1 1 2 2 3 2 1 1 2 2 1 1 3 1 3 1 3 2 3 3 1 3 2 3 3 3 3 3 1 1 1 2 2 3 2 3 3 3 1 3 3 2 1 1 1 1 2 2 2 1 2 2 3 2 1 3 2 1 3 3 3 3 2 3 1 1 3 2 2 2 2 1 2 2 2 1 1 1 2 3 2 2 3 2 2 3 1 2 2 3 3 2 3 2 1 1 1 3 1 3 3 3 2 3 2 3 3 3 3 1 1 3 2 2 1 3 1 1 3 1 1 3 2 1 3 3...
output:
191 1 2 1 4 1 8 1 10 1 11 1 18 1 19 1 22 1 23 1 25 1 28 1 29 1 37 1 42 1 51 1 52 1 54 1 61 1 66 1 67 1 68 1 70 1 71 1 73 1 76 1 82 1 87 1 88 1 89 1 90 1 92 1 93 1 94 2 2 2 4 2 5 2 7 2 8 2 11 2 12 2 15 2 17 2 26 2 28 2 36 2 37 2 46 2 54 2 60 2 61 2 62 2 64 2 66 2 70 2 75 2 76 2 80 2 81 2 84 2 86 2 87...
result:
ok 192 lines
Test #22:
score: 0
Accepted
time: 206ms
memory: 139224kb
input:
1 1 6 80 23 5 3 7 7 4 5 3 3 7 6 3 3 6 1 4 6 5 7 2 6 2 5 6 2 1 4 5 1 6 6 2 1 1 5 1 1 3 5 6 5 7 4 7 4 4 2 7 1 5 1 2 1 1 4 3 3 4 3 2 1 6 1 1 6 7 5 4 7 1 7 4 6 3 7 7 2 5 1 7 5 3 4 3 6 2 2 2 3 3 1 2 5 7 7 4 5 7 7 5 1 2 2 6 6 4 6 1 2 4 1 5 6 1 7 4 3 1 3 2 5 3 1 7 2 6 4 2 2 6 5 4 2 1 5 1 3 6 7 1 3 6 7 4 4 ...
output:
277 1 10 1 13 1 16 1 20 1 23 2 6 2 7 2 16 3 15 3 18 4 3 4 15 5 11 5 12 5 14 5 20 6 10 6 14 6 22 7 3 7 8 7 12 7 14 7 16 8 13 8 23 9 1 9 3 9 14 9 21 10 3 10 12 10 14 10 15 10 21 11 1 11 5 11 9 11 13 11 20 12 9 12 18 13 7 13 8 13 12 13 18 13 19 13 21 14 16 14 19 15 5 15 14 17 2 17 12 17 19 17 23 18 4 1...
result:
ok 278 lines
Test #23:
score: 0
Accepted
time: 1ms
memory: 7824kb
input:
1 3 94 82 89 4 2 32 23 91 15 19 42 54 45
output:
0
result:
ok single line: '0'
Test #24:
score: -100
Wrong Answer
time: 210ms
memory: 140704kb
input:
1 4 0 0 1 0 65 88 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ...
output:
5720 1 1 1 2 1 3 1 4 1 5 1 6 1 7 1 8 1 9 1 10 1 11 1 12 1 13 1 14 1 15 1 16 1 17 1 18 1 19 1 20 1 21 1 22 1 23 1 24 1 25 1 26 1 27 1 28 1 29 1 30 1 31 1 32 1 33 1 34 1 35 1 36 1 37 1 38 1 39 1 40 1 41 1 42 1 43 1 44 1 45 1 46 1 47 1 48 1 49 1 50 1 51 1 52 1 53 1 54 1 55 1 56 1 57 1 58 1 59 1 60 1 61...
result:
wrong answer 1st lines differ - expected: '5525', found: '5720'