QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#341246 | #7398. Triangle Tiling | Skyjoy | WA | 2ms | 6012kb | C++14 | 2.1kb | 2024-02-29 16:50:46 | 2024-02-29 16:50:46 |
Judging History
answer
#include<bits/stdc++.h>
#define I using
#define love namespace
#define Elaina std
I love Elaina;
const int N=5010;
int read(){
int x=0,f=1;
char ch=getchar();
while(ch<'0'||ch>'9'){
if(ch=='-')f=-1;
ch=getchar();
}
while(ch>='0'&&ch<='9'){
x=(x<<3)+(x<<1)+ch-'0';
ch=getchar();
}
return x*f;
}
int T,n,a[N][N];
vector<int>pos[N],vec[N];
char ans[N][N];
namespace AyaseEli{
#define ls(k) (k<<1)
#define rs(k) (k<<1|1)
int maxn[N<<2],tag[N<<2];
void pushup(int k){maxn[k]=max(maxn[ls(k)],maxn[rs(k)])+tag[k];}
void build(int k,int l,int r){
tag[k]=0;
if(l==r){
maxn[k]=l-1;
return;
}
int mid=(l+r)/2;
build(ls(k),l,mid),build(rs(k),mid+1,r);
pushup(k);
}
void change(int k,int l,int r,int qr){
if(r<=qr){
maxn[k]++,tag[k]++;
return;
}
int mid=(l+r)/2;
change(ls(k),l,mid,qr);
if(mid<qr)change(rs(k),mid+1,r,qr);
pushup(k);
}
int query(int k,int l,int r,int qr){
if(r<=qr)return maxn[k];
int mid=(l+r)/2,res=query(ls(k),l,mid,qr);
if(mid<qr)res=max(res,query(rs(k),mid+1,r,qr));
return res+tag[k];
}
}
I love AyaseEli;
void solve(){
n=read();
for(int i=0;i<=n;i++)vec[i].clear();
for(int i=1;i<=n;i++){
pos[i].clear();
ans[i][i+1]=0;
for(int j=1;j<=i;j++){
scanf("%1d",&a[i][j]);
if(!a[i][j]){
ans[i][j]='-';
pos[i].push_back(j),vec[i-j].push_back(j);
}
}
}
for(int i=n+1;i>1;i--){
build(1,1,i-1);
if(pos[i].empty()&&i<=n){
puts("Impossible!");
return;
}
for(int j=1,l=0,r=0;j<=i;j++){
for(int tmp:vec[i-1-j]){
if(tmp>=j)break;
change(1,1,i-1,tmp);
}
if(!a[i][j]&&i<=n){
a[i-1][r]=0,ans[i-1][r]='2';
pos[i-1].push_back(r);
for(int k=l+1;k<=r;k++)ans[i][k]='1';
for(int k=r+1;k<j;k++)ans[i][k]='3';
if(r)change(1,1,i-1,r);
l=r=j;
}
if(i==j){
for(int k=l+1;k<=i;k++)ans[i][k]='1';
break;
}
if(query(1,1,i-1,j)>j){
puts("Impossible!");
return;
}
if(l&&query(1,1,i-1,l)>=j)r=j+1;
}
}
for(int i=1;i<=n;i++)printf("%s\n",ans[i]+1);
}
int main(){
T=read();
while(T--)solve();
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 1ms
memory: 5996kb
input:
1 4 0 11 010 1101
output:
- 21 -3- 33-1
result:
ok ok
Test #2:
score: -100
Wrong Answer
time: 2ms
memory: 6012kb
input:
909 6 0 11 100 1111 11100 111110 7 0 11 011 1001 10111 100111 1111111 6 0 00 001 1111 11101 111111 8 1 01 111 1111 10111 101110 1101101 11111100 2 1 00 2 0 01 3 0 01 110 7 1 00 011 1010 11011 110111 1111111 8 1 11 111 1011 11010 011110 1101110 01111111 5 1 00 010 1111 10111 6 0 10 011 0101 01111 111...
output:
- 32 3-- 3332 333-- 33333- Impossible! Impossible! - -1 111 3211 32211 3-2332 33-33-2 333333-- 2 -- - -1 - -1 33- Impossible! - 21 221 2-21 2323- -3233- 33-333- -1111111 2 2- -3- 1111 3-111 Impossible! Impossible! - -1 332 33-- 2 -- 2 -- 2 11 211 -332 333-- - 21 --1 - -1 - -1 211 23-1 2-111 23-111 -...
result:
wrong answer jury does not has a solution while user does