QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#525412#2898. DiagonalsZhouShangTL 7ms3748kbC++202.0kb2024-08-20 16:15:162024-08-20 16:15:16

Judging History

你现在查看的是最新测评结果

  • [2024-08-20 16:15:16]
  • 评测
  • 测评结果:TL
  • 用时:7ms
  • 内存:3748kb
  • [2024-08-20 16:15:16]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define int ll
#define rep(i,a,b) for (int i = a; i < (b); i++)
#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
#define PB push_back
#define FS first
#define SD second
#define ary(k) array<int, k>
template<class A, class B> void cmx(A &x, B y) { x = max<A>(x, y);}
template<class A, class B> void cmn(A &x, B y) { x = min<A>(x, y);}
typedef pair<int, int> pii;
typedef vector<int> vi;
int n,f[99],a[99][99],z[99];
string s[99];
int C(int x,int y){
    return (x-1)*(n+1)+y;
}
int F(int x){
    return f[x]==x?x:f[x]=F(f[x]);
}
void D(int x,int y){
    if(x>n){
        for(int i=1;i<=n+1;i++)
            for(int j=1;j<=n+1;j++){
                int c=C(i,j);
                if(!(s[i][j]=='+'||s[i][j]-'0'==z[c]))
                    return;
            }
        for(int i=1;i<=(n+1)*(n+1);i++)
            f[i]=i;
        for(int i=1;i<=n;i++)
            for(int j=1;j<=n;j++){
                int u,v;
                if(a[i][j])
                    u=C(i,j),v=C(i+1,j+1);
                else
                    u=C(i,j+1),v=C(i+1,j);
                if(F(u)==F(v))
                    return;
                f[F(u)]=F(v);
            }
        for(int i=1;i<=n;i++,cout<<'\n')
            for(int j=1;j<=n;j++)
                cout<<(a[i][j]?"\\":"/");
        exit(0);
    }
    int u=x,v=y+1;
    if(v>n)
        v-=n,u++;
    for(int i=0;i<=1;i++){
        a[x][y]=i;
        if(i)
            z[C(x,y)]++,z[C(x+1,y+1)]++;
        else
            z[C(x,y+1)]++,z[C(x+1,y)]++;
        if(s[x][y]=='+'||s[x][y]-'0'==z[C(x,y)])
            D(u,v);
        if(i)
            z[C(x,y)]--,z[C(x+1,y+1)]--;
        else
            z[C(x,y+1)]--,z[C(x+1,y)]--;
    }
}
signed main() {
    //cin.tie(0)->sync_with_stdio(0); cin.exceptions(cin.failbit);
    cin>>n;
    for(int i=1;i<=n+1;i++)
        cin>>s[i],s[i]=' '+s[i];
    D(1,1);
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 5ms
memory: 3592kb

input:

8
+11+111++
1++++1++0
1++2++3++
+1+2+1+3+
+213+++++
12+232+++
222+++22+
+++3+3+++
+211+121+

output:

////////
/\\/\//\
/\\///\\
//\/\//\
///////\
////\\\\
\\\/\///
\///\\//

result:

ok 8 lines

Test #2:

score: 0
Accepted
time: 1ms
memory: 3556kb

input:

8
++++++11+
+13+13++1
++21+21++
+11+2222+
+2++3++21
+11+1+2+1
+++322+1+
11+1+1+11
+1++1++++

output:

/\/\\///
\\\\//\/
/\\////\
\\/////\
//\/\//\
\//////\
/\/\\\//
//\\\/\/

result:

ok 8 lines

Test #3:

score: 0
Accepted
time: 7ms
memory: 3528kb

input:

8
++1+++2++
12++23++2
0222322++
+3+11+3+1
++++++++1
+213+2++0
+1+3++22+
2++22+4++
+1+++1+++

output:

\\\\\/\\
\\\\\\\/
////\\\/
/\\///\/
/\\//\\/
/\///\/\
///\/\/\
\\/\//\\

result:

ok 8 lines

Test #4:

score: 0
Accepted
time: 0ms
memory: 3748kb

input:

5
+1+2++
1++11+
+3+2++
02+++1
++3+1+
+1+++1

output:

\\/\\
\/\\/
\\\\\
////\
//\\\

result:

ok 5 lines

Test #5:

score: 0
Accepted
time: 0ms
memory: 3620kb

input:

5
+++21+
11+2++
1++2++
++32+1
+3++3+
++0+++

output:

\\/\\
\//\/
\\/\/
\//\/
//\\\

result:

ok 5 lines

Test #6:

score: 0
Accepted
time: 0ms
memory: 3596kb

input:

5
++1+++
12+++1
+2121+
+2+22+
+323++
++++1+

output:

////\
////\
\\///
\\///
/\/\\

result:

ok 5 lines

Test #7:

score: -100
Time Limit Exceeded

input:

8
+++++++++
++4+++22+
+3+++3+3+
++++2+3++
++1++++21
++21++3++
+2+++++21
+4+1+2+11
++++2+1+0

output:


result: