QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #261160 | #7740. Puzzle: Question Mark | ucup-team1447 | WA | 200ms | 6180kb | C++14 | 11.9kb | 2023-11-22 18:29:50 | 2023-11-22 18:29:50 |
Judging History
answer
// dottle bot
#ifndef ONLINE_JUDGE
#define DEBUG
#endif
#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <queue>
#include <vector>
#include <bitset>
#include <map>
#include <assert.h>
#include <math.h>
#include <set>
#include <random>
std::mt19937_64 rnd(586666);
#define nln puts("")
#define od(x) printf("%d",x)
#define odb(x) printf("%d ",x)
#define odl(x) printf("%d\n",x)
#define odp(x,y) printf("%d %d\n",x,y)
#define ol(x) puts("")
#define old(x) printf("%lld",x)
#define oldb(x) printf("%lld ",x)
#define oldl(x) printf("%lld\n",x)
#define oldp(x,y) printf("%lld %lld\n",x,y)
#define rg(x) for(int i=1;i<=(x);i++){
#define rg_(i,x) for(int i=1;i<=(x);i++){
#define fe(u) for(int i=h[u];i;i=e[i].nxt){int v=e[i].v;
#define gr }
#define rrg(x) for(int i=0;i<(x);i++){
#define rdln(a) a[i]=read();
#define rdln0(a,x) rrg(x) rdln(a) gr
#define rdln1(a,x) rg(x) rdln(a) gr
#define int long long
const int mod=1e9+7;
#ifdef int
#define inf 0x3f3f3f3f3f3f3f3fll
#else
#define inf 0x3f3f3f3f
#endif
inline int min(int a,int b){return a>b?b:a;}
inline int max(int a,int b){return a<b?b:a;}
#define cmlSEGMIN
#define cmlSEGMAX
#define cmlSEGSUM
class SegTreeAl{
#ifdef cmlSEGMIN
int minn[1000005<<2];
#endif
#ifdef cmlSEGMAX
int maxn[1000005<<2];
#endif
#ifdef cmlSEGSUM
int sum[1000005<<2];
#endif
int tag[1000005<<2];
#ifdef cmlSEGSUM
void pushdown(int o,int l,int r)
#else
void pushdown(int o)
#endif
{
int&t=tag[o];
#ifdef cmlSEGMIN
minn[o<<1]+=t;
minn[o<<1|1]+=t;
#endif
#ifdef cmlSEGMAX
maxn[o<<1]+=t;
maxn[o<<1|1]+=t;
#endif
#ifdef cmlSEGSUM
int m=l+r>>1;
sum[o<<1]+=t*(m-l+1);
sum[o<<1|1]+=t*(r-m);
#endif
tag[o<<1]+=t;
tag[o<<1|1]+=t;
t=0;
}
void add(int o,int l,int r,int L,int R,int v)
{
if(L<=l&&r<=R)
{
#ifdef cmlSEGMAX
maxn[o]+=v;
#endif
#ifdef cmlSEGMIN
minn[o]+=v;
#endif
#ifdef cmlSEGSUM
sum[o]+=v*(r-l+1);
#endif
tag[o]+=v;
return;
}
int m=l+r>>1;
#ifdef cmlSEGSUM
pushdown(o,l,r);
#else
pushdown(o);
#endif
if(L<=m)add(o<<1,l,m,L,R,v);
if(m<R)add(o<<1|1,m+1,r,L,R,v);
#ifdef cmlSEGMAX
maxn[o]=max(maxn[o<<1],maxn[o<<1|1]);
#endif
#ifdef cmlSEGMIN
minn[o]=min(minn[o<<1],minn[o<<1|1]);
#endif
#ifdef cmlSEGSUM
sum[o]=sum[o<<1]+sum[o<<1|1];
#endif
}
#ifdef cmlSEGMIN
int qmin(int o,int l,int r,int L,int R)
{
if(L<=l&&r<=R)
{
return minn[o];
}
int m=l+r>>1,res=inf;
#ifdef cmlSEGSUM
pushdown(o,l,r);
#else
pushdown(o);
#endif
if(L<=m)res=min(res,qmin(o<<1,l,m,L,R));
if(m<R)res=min(res,qmin(o<<1|1,m+1,r,L,R));
#ifdef cmlSEGMAX
maxn[o]=max(maxn[o<<1],maxn[o<<1|1]);
#endif
#ifdef cmlSEGMIN
minn[o]=min(minn[o<<1],minn[o<<1|1]);
#endif
#ifdef cmlSEGSUM
sum[o]=sum[o<<1]+sum[o<<1|1];
#endif
return res;
}
#endif
#ifdef cmlSEGMAX
int qmax(int o,int l,int r,int L,int R)
{
if(L<=l&&r<=R)
{
return maxn[o];
}
int m=l+r>>1,res=-inf;
#ifdef cmlSEGSUM
pushdown(o,l,r);
#else
pushdown(o);
#endif
if(L<=m)res=max(res,qmax(o<<1,l,m,L,R));
if(m<R)res=max(res,qmax(o<<1|1,m+1,r,L,R));
#ifdef cmlSEGMAX
maxn[o]=max(maxn[o<<1],maxn[o<<1|1]);
#endif
#ifdef cmlSEGMIN
minn[o]=min(minn[o<<1],minn[o<<1|1]);
#endif
#ifdef cmlSEGSUM
sum[o]=sum[o<<1]+sum[o<<1|1];
#endif
return res;
}
#endif
#ifdef cmlSEGSUM
int qsum(int o,int l,int r,int L,int R)
{
if(L<=l&&r<=R)
{
return sum[o];
}
int m=l+r>>1,res=0;
#ifdef cmlSEGSUM
pushdown(o,l,r);
#else
pushdown(o);
#endif
if(L<=m)res+=qsum(o<<1,l,m,L,R);
if(m<R)res+=qsum(o<<1|1,m+1,r,L,R);
#ifdef cmlSEGMAX
maxn[o]=max(maxn[o<<1],maxn[o<<1|1]);
#endif
#ifdef cmlSEGMIN
minn[o]=min(minn[o<<1],minn[o<<1|1]);
#endif
#ifdef cmlSEGSUM
sum[o]=sum[o<<1]+sum[o<<1|1];
#endif
return res;
}
#endif
};
#define newe(n) struct Edge{int v,w,nxt;}e[2*n+5];\
typedef int arr[n+5];\
arr h;\
int cnt=1;\
inline void addedge(int u,int v,int w){e[cnt]=(Edge){v,w,h[u]};h[u]=cnt++;}\
struct node{\
int u,d;\
bool operator<(const node&b)const{return d>b.d;}\
};\
void dij(int s,int *d,int N)\
{\
memset(d,0x3f,sizeof(int)*(N+3));\
d[s]=0;std::priority_queue<node>q;q.push((node){s,0});\
while(!q.empty())\
{\
int u=q.top().u,D=q.top().d;q.pop();if(D!=d[u])continue;\
for(int i=h[u];i;i=e[i].nxt){int v=e[i].v,w=e[i].w;\
if(d[u]+w<d[v])d[v]=d[u]+w,q.push((node){v,d[v]});\
}\
}\
}
#define mgs int fa[1<<22],sz[1<<22];\
inline int f(int x){return x==fa[x]?x:fa[x]=f(fa[x]);}\
inline int uf(int x,int y)\
{\
int fx=f(x),fy=f(y);\
if(fx==fy)return 0;\
if(sz[fx]>sz[fy])fx^=fy^=fx^=fy;\
fa[fx]=fy,sz[fy]+=sz[fx];\
return 1;\
}
inline int read()
{
int num=0,f=1;char c=getchar();
while(c<48||c>57){if(c=='-')f=-1;c=getchar();}
while(c>47&&c<58)num=num*10+(c^48),c=getchar();
return num*f;
}
inline int re1d()
{
char c=getchar();
while(c<48||c>49)c=getchar();
return c&1;
}
#ifdef cmlBIT
struct BIT{int a[1<<20|1],n;
void add(int x,int p){while(x<=n)a[x]+=p,x+=x&-x;}
int operator[](int x){int res=0;while(x)res+=a[x],x-=x&-x;return res;}
int operator()(int l,int r){return (*this)[r]-(*this)[l-1];}};
#endif
int rnv[1000005];
// #define COMB
#ifdef COMB
#ifndef int
#define int long long
#endif
int fac[1000005],inv[1000005];
#endif
void initprog()
{
#ifdef COMB
fac[0]=inv[0]=inv[1]=1;
rg(1000000)fac[i]=fac[i-1]*i%mod;gr
rg(1000000)if(i>1)inv[i]=inv[mod%i]*(mod-mod/i)%mod;gr
rg(1000000)rnv[i]=inv[i];gr
rg(1000000)inv[i]=inv[i]*inv[i-1]%mod;gr
#endif
}
#ifdef COMB
int C(int n,int m)
{
if(n==m||m==0)return 1;
if(n<m)return 0;
return fac[n]*inv[m]%mod*inv[n-m]%mod;
}
#endif
inline int qp(int a,int b){int c=1;while(b){if(b&1)c=c*a%mod;a=a*a%mod;b>>=1;}return c;}
inline int mae(int &a,int b){a+=b;if(a>=mod)a-=mod;return a;}
inline int mde(int &a,int b){a+=mod-b;if(a>=mod)a-=mod;return a;}
inline int mle(int &a,int b){a=a*b%mod;return a;}
inline int mve(int &a,int b){a=a*qp(b,mod-2)%mod;return a;}
inline int mxe(int &a,int b){return a=a>b?a:b;}
inline int mne(int &a,int b){return a=a<b?a:b;}
inline int ae(int a,int b){int c=a+b;return c>=mod?c-mod:c;}
inline int de(int a,int b){return ae(a,mod-b);}
inline int me(int a,int b){return a*b%mod;}
inline int mive(int &a,int b){a=a*rnv[b]%mod;return a;}
inline int ive(int a,int b){return a*rnv[b]%mod;}
inline int ve(int a,int b){return a*qp(b,mod-2)%mod;}
#ifdef cmlST
struct STmin{
int a[21][1000005],n;
void init(int N,int *b)
{
n=N;
rg(n)a[0][i]=b[i];gr
rg(20)rg_(j,n-(1<<i)+1)a[i][j]=min(a[i-1][j],a[i-1][j+(1<<i-1)]);gr gr
}
int q(int l,int r)
{
int d=std::__lg(r-l+1);
return min(a[d][l],a[d][r-(1<<d)+1]);
}
};
struct STmax{
int a[21][1000005],n;
void init(int N,int *b)
{
n=N;
rg(n)a[0][i]=b[i];gr
rg(20)rg_(j,n-(1<<i)+1)a[i][j]=max(a[i-1][j],a[i-1][j+(1<<i-1)]);gr gr
}
int q(int l,int r)
{
int d=std::__lg(r-l+1);
return max(a[d][l],a[d][r-(1<<d)+1]);
}
};
#endif
#ifdef cmlSAM
struct SAM{
int ch[1000005][26],lnk[1000005],len[1000005],lst=1,cc=1;
int sz[1000005];
void insert(int c)
{
len[++cc]=len[lst]+1;sz[cc]=1;
int p=lst;lst=cc;
while(p&&ch[p][c]==0)ch[p][c]=cc,p=lnk[p];
if(p==0)lnk[cc]=1;
else
{
int x=ch[p][c];
if(len[p]+1==len[x])lnk[cc]=x;
else
{
int q=cc;++cc;
lnk[cc]=lnk[x];
lnk[x]=lnk[q]=cc;
len[cc]=len[p]+1;
memcpy(ch[cc],ch[x],sizeof(ch[cc]));
while(p&&ch[p][c]==x)ch[p][c]=cc,p=lnk[p];
}
}
}
newe(1000005);
long long ans;
void build()
{
rg(cc)addedge(lnk[i],i,0);gr
}
void dfs(int u)
{
fe(u)dfs(v),sz[u]+=sz[v];gr
if(sz[u]>1)ans=max(ans,1ll*sz[u]*len[u]);
}
}t;
#endif
int a[2005][2005];
int n;
void print()
{
rg(n)rg_(j,n)if(j==n)od(a[i][j]);else odb(a[i][j]);gr puts("");gr
}
void solve()
{
int cc=0;
auto rect=[&](int x,int y,int d)
{
if(d==0)
{
++cc;
a[x][y+0]=cc;
a[x][y+1]=cc;
a[x][y+2]=cc;
a[x][y+3]=cc;
a[x+1][y+0]=cc;
a[x+1][y+1]=cc;
a[x+1][y+2]=cc;
a[x+1][y+3]=cc;
a[x][y]=a[x+1][y]=a[x][y+1]=a[x+1][y+2]=++cc;
}
else
{
++cc;
a[x+0][y+0]=cc;
a[x+1][y+0]=cc;
a[x+2][y+0]=cc;
a[x+3][y+0]=cc;
a[x+0][y+1]=cc;
a[x+1][y+1]=cc;
a[x+2][y+1]=cc;
a[x+3][y+1]=cc;
a[x][y]=a[x+1][y]=a[x][y+1]=a[x+2][y+1]=++cc;
}
};
if(n<=2)
{
puts("0");
print();
return;
}
if(n==3)
{
puts("2");
a[1][3]=a[1][2]=a[2][2]=a[3][3]=1;
a[2][1]=a[2][3]=a[3][1]=a[3][2]=2;
print();
return;
}
if(n%4==0)
{
int res=n*n/4;
odl(res);
for(int x=1;x<=n;x+=2)
for(int y=1;y<=n;y+=4)
rect(x,y,0);
return print();
}
if(n%4==2)
{
int res=n*n/4-1;
odl(res);
for(int x=1;x<=n;x+=2)
for(int y=1;y+3<=n;y+=4)
rect(x,y,0);
for(int x=1;x+3<=n;x+=4)rect(x,n-1,1);
return print();
}
auto get5=[&](int x,int y)
{
int b[5][5]={};
b[0][0]=b[0][1]=b[1][0]=b[1][2]=++cc;
b[0][2]=b[1][1]=b[2][1]=b[2][2]=++cc;
b[3][0]=b[3][2]=b[4][0]=b[4][1]=++cc;
for(int i=0;i<5;i++)
for(int j=0;j<5;j++)
if(b[i][j])
a[x+i][y+j]=b[i][j];
rect(x,y+3,1);
};
auto place=[&](int x,int y)
{
x-=2,y-=2;
a[x][y+1]=a[x][y+2]=a[x+1][y+1]=a[x+2][y+2]=++cc;
a[x+1][y]=a[x+1][y+2]=a[x+2][y]=a[x+2][y+1]=++cc;
};
auto get9=[&](int x,int y)
{
int b[9][9]={
9,9,8,2,4,4,3,5,3,
9,8,9,4,2,4,3,3,5,
0,8,8,2,2,1,1,5,5,
10,11,10,6,1,6,1,0,0,
11,10,10,6,6,0,0,0,0,
11,11,12,12,0,0,0,0,0,
15,15,12,13,0,0,0,0,0,
14,15,14,12,13,0,0,0,0,
15,14,14,13,13
};
cc+=15;
for(int i=0;i<9;i++)
for(int j=0;j<9;j++)
if(b[i][j])
a[x+i][y+j]=b[i][j];
rect(x+3,y+7,1);
place(x+6,y+6);
rect(x+7,y+5,0);
};
if(n==5)
{
get5(1,1);
odl(n*n/4-1);
return print();
}
if(n==7)
{
get5(1,1);
odl(n*n/4-1);
place(n,n);
for(int j=1;j+3<=n;j+=4)rect(n-1,j,0),rect(j,n-1,1);
return print();
}
if(n%4==1)
{
odl(n*n/4);
int x=(n+1)/2-2-2,y=x+3+2;
get9(x,1);
for(int i=9;i<n;i+=4)
{
x-=2;y+=2;
for(int j=1;j<=i-2;j+=4)
rect(x,j,0),rect(y,j,0);
{
int s=x,t=i;
a[s][t]=a[s+1][t]=a[s][t+1]=a[s+1][t+2]=++cc;
a[s][t+2]=a[s+1][t+1]=a[s+2][t+2]=a[s+2][t+1]=++cc;
}
{
int s=y-1,t=i-1;
a[s-1][t+2]=a[s-1][t+3]=a[s][t+3]=a[s+1][t+2]=++cc;
a[s][t+2]=a[s+1][t+1]=a[s+2][t+2]=a[s+2][t+1]=++cc;
// odp(y+1,i+4);
place(y+1,i+4);
}
{
int s=x,t=i+3;
for(int j=0;j<i/4;j++)
{
rect(s,t,1);
s+=4;
}
}
{
int s=x+3,t=i+1;
for(int j=1;j<i/4;j++)
{
rect(s,t,1);
s+=4;
}
a[s][t]=a[s+1][t]=a[s][t+1]=a[s+1][t+2]=++cc;
a[s+1][t+1]=a[s+1][t+3]=a[s+2][t+2]=a[s+2][t+3]=++cc;
}
}
print();
}
else
{
odl(n*n/4);
n-=2;
int x=(n+1)/2-2-2,y=x+3+2;
get9(x,1);
for(int i=9;i<n;i+=4)
{
x-=2;y+=2;
for(int j=1;j<=i-2;j+=4)
rect(x,j,0),rect(y,j,0);
{
int s=x,t=i;
a[s][t]=a[s+1][t]=a[s][t+1]=a[s+1][t+2]=++cc;
a[s][t+2]=a[s+1][t+1]=a[s+2][t+2]=a[s+2][t+1]=++cc;
}
{
int s=y-1,t=i-1;
a[s-1][t+2]=a[s-1][t+3]=a[s][t+3]=a[s+1][t+2]=++cc;
a[s][t+2]=a[s+1][t+1]=a[s+2][t+2]=a[s+2][t+1]=++cc;
// odp(y+1,i+4);
place(y+1,i+4);
}
{
int s=x,t=i+3;
for(int j=0;j<i/4;j++)
{
rect(s,t,1);
s+=4;
}
}
{
int s=x+3,t=i+1;
for(int j=1;j<i/4;j++)
{
rect(s,t,1);
s+=4;
}
a[s][t]=a[s+1][t]=a[s][t+1]=a[s+1][t+2]=++cc;
a[s+1][t+1]=a[s+1][t+3]=a[s+2][t+2]=a[s+2][t+3]=++cc;
}
}
n+=2;
place(n,n);
for(int j=1;j+3<=n;j+=4)rect(n-1,j,0),rect(j,n-1,1);
print();
}
}
signed main()
{
initprog();
int T=read();rg(T)
n=read();
rg(n)rg_(j,n)a[i][j]=0;gr gr
solve();
gr
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 1508kb
input:
2 3 4
output:
2 0 1 1 2 1 2 2 2 1 4 2 2 1 1 2 1 2 1 4 4 3 3 4 3 4 3
result:
ok Correct. (2 test cases)
Test #2:
score: -100
Wrong Answer
time: 200ms
memory: 6180kb
input:
246 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 101 ...
output:
0 0 0 0 0 0 0 2 0 1 1 2 1 2 2 2 1 4 2 2 1 1 2 1 2 1 4 4 3 3 4 3 4 3 5 1 1 2 5 5 1 2 1 5 4 0 2 2 4 5 3 0 3 4 4 3 3 0 0 0 8 2 2 1 1 8 8 2 1 2 1 8 7 4 4 3 3 7 8 4 3 4 3 7 7 6 6 5 5 0 0 6 5 6 5 0 0 11 1 1 2 5 5 11 11 1 2 1 5 4 11 10 0 2 2 4 5 10 11 3 0 3 4 4 10 10 3 3 0 0 0 6 6 9 9 8 8 7 6 7 9 8 9 8 7 7...
result:
wrong answer Integer parameter [name=a_ij] equals to 21, violates the range [0, 20] (test case 9)