QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#587880#6432. Puzzle in InazumaNianFengWA 1ms7668kbC++146.6kb2024-09-24 22:13:372024-09-24 22:13:37

Judging History

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

  • [2024-09-24 22:13:37]
  • 评测
  • 测评结果:WA
  • 用时:1ms
  • 内存:7668kb
  • [2024-09-24 22:13:37]
  • 提交

answer

#include <cstdio>
#include <string>
#include <vector>
#include <tuple>
#define i128 __int128
#define i64 long long
#define uit unsigned int
#define ull unsigned i64
template <class T> bool chkmax(T &x,T y){ return x<y?x=y,true:false; }
template <class T> bool chkmin(T &x,T y){ return x>y?x=y,true:false; }
using namespace std;
namespace io{
    #define file(s,x)\
        freopen(#s#x".in","r",stdin);\
        freopen(#s".out","w",stdout);
    const int SIZE=1<<21;
    short plc[50],rof=0;
    char ibuf[SIZE],*p1=ibuf,*p2=ibuf,obuf[SIZE],*p3=obuf;
    #define flush() (fwrite(obuf,1,p3-obuf,stdout),p3=obuf)
    #define gc() (p1==p2&&(p2=(p1=ibuf)+fread(ibuf,1,SIZE,stdin),p1==p2)?EOF:*p1++)
    #define pc(ch) (p3==obuf+SIZE&&flush(),*p3++=ch)
    class Flush{ public: ~Flush(){ flush(); } }_;
    template <class T> inline void read(T &x){
        x=0; bool flag=true; char c=gc();
        while(!isdigit(c)){ if(c=='-') flag=false; c=gc(); }
        while(isdigit(c)){ x=(x<<1)+(x<<3)+(c^48); c=gc(); }
        !flag&&(x=~(x-1));
    }
    inline void read(char &c){ while((c=gc())<'a'||c>'z'); }
    inline void read(string &s){
        s=""; char c; while((c=gc())<'a'||c>'z') ;
        s+=c; while((c=gc())>='a'&&c<='z') s+=c;
    }
    template <class T,class ...Args>
    inline void read(T &first,Args &...args){
        read(first);
        read(args...);
    }
    template <class T> inline void print(T x){
        x<0?pc('-'),x=-x:0;
        do plc[++rof]=x%10; while(x/=10);
        while(rof) pc(plc[rof--]|48);
    }
    inline void print(char c){ pc(c); }
    inline void print(string s){ for(char c : s) pc(c); }
    inline void print(const char *s){ print(string(s)); }
    template <class T,class ...Args>
    inline void print(T first,Args ...args){
        print(first);
        print(args...);
    }
}
using namespace io;
const int N=105;
int n,a[N][N];
int b[10][10];
bool GJ(){
    for(int i=1;i<=4;i++){
        int tmp=i;
        for(int j=i;j<=6;j++)
            if(b[j][i]){
                tmp=j;
                break;
            }
        if(tmp!=i)
            swap(b[tmp],b[i]);
        if(!b[i][i]) continue;
        for(int k=1;k<=6;k++){
            if(k==i) continue;
            for(int j=5;j>=i;j--)
                b[k][j]-=b[k][i]*b[i][j]/b[i][i];
        }
    }
    if(b[5][5]||b[6][5])
        return false;
    for(int i=1;i<=4;i++)
        if(!b[i][i]&&b[i][5])
            return false;
        else if(b[i][i])
            b[i][5]/=b[i][i];
    return true;
}
struct Answer{
    int a,b,c,d,x;
};
vector<Answer>ans;
tuple<int,int,int>mex(int i,int j,int k){
    int x=1,y=1,z=1;
    while(x==i||x==j||x==k) x++;
    while(y==i||y==j||y==k||y==x) y++;
    while(z==i||z==j||z==k||z==x||z==y) z++;
    return make_tuple(x,y,z);
}
int tot;
bool use[6];
int nod[6][5]={
    {0,0,0,0,0},
    {0,2,3,4,5},
    {0,1,3,4,5},
    {0,1,2,4,5},
    {0,1,2,3,5},
    {0,1,2,3,4}
};
#define t(i) nod[x][i]
void solve(int x){
    if(x>5) return;
    if(tot==0){
        for(int i=1;i<=5;i++)
            if(use[i]) ans.push_back({t(1),t(2),t(3),t(4),1});
        for(int i=1;i<=5;i++)
            for(int j=1;j<=5;j++){
                if(j==i) continue;
                int k=j+1;
                if(k==i) k++;
                if(k>n||!a[i][j])
                    continue;
                auto [x,y,z]=mex(i,j,k);
                ans.push_back({j,i,x,k,-a[i][j]/2});
                ans.push_back({k,i,y,j,a[i][j]/2});
                ans.push_back({j,i,y,k,-a[i][j]/2});
                ans.push_back({k,i,x,j,a[i][j]/2});
                ans.push_back({j,i,x,y,a[i][j]});
                ans.push_back({k,i,x,y,-a[i][j]});
            }
        print(ans.size(),'\n');
        for(auto tmp : ans)
            print(tmp.a,' ',tmp.b,' ',tmp.c,' ',tmp.d,' ',tmp.x,'\n');
        exit(0);
    }
    solve(x+1);
    use[x]=true;
    for(int i=2;i<=4;i++){
        a[t(1)][t(i)]++;
        a[t(i)][t(1)]++;
        tot+=a[t(1)][t(i)]&1?1:-1;
    }
    for(int i=2;i<4;i++)
        for(int j=i+1;j<=4;j++){
            a[t(i)][t(j)]--;
            a[t(j)][t(i)]--;
            tot+=a[t(i)][t(j)]&1?1:-1;
        }
    solve(x+1);
    for(int i=2;i<=4;i++){
        a[t(1)][t(i)]--;
        a[t(i)][t(1)]--;
        tot+=a[t(1)][t(i)]&1?1:-1;
    }
    for(int i=2;i<4;i++)
        for(int j=i+1;j<=4;j++){
            a[t(i)][t(j)]++;
            a[t(j)][t(i)]++;
            tot+=a[t(i)][t(j)]&1?1:-1;
        }
    use[x]=false;
}
int main(){
    read(n);
    for(int i=1;i<n;i++)
        for(int j=i+1;j<=n;j++)
            read(a[i][j]);
    int sum=0;
    for(int i=1;i<n;i++)
        for(int j=i+1;j<=n;j++){
            int x; read(x);
            a[i][j]=x-a[i][j];
            sum+=a[i][j];
        }
    if(sum)
        return print("-1\n"),0;
    if(n==4){
        b[1][1]=b[1][2]=1,b[1][3]=b[1][4]=-1,b[1][5]=a[1][2];
        b[2][1]=b[2][3]=1,b[2][2]=b[2][4]=-1,b[2][5]=a[1][3];
        b[3][1]=b[3][4]=1,b[3][2]=b[3][3]=-1,b[3][5]=a[1][4];
        b[4][2]=b[4][3]=1,b[4][1]=b[4][4]=-1,b[4][5]=a[2][3];
        b[5][2]=b[5][4]=1,b[5][1]=b[5][3]=-1,b[5][5]=a[2][4];
        b[6][3]=b[6][4]=1,b[6][1]=b[6][2]=-1,b[6][5]=a[3][4];
        if(!GJ()) return print("-1\n"),0;
        print("4\n");
        print("1 2 3 4 ",b[1][5],'\n');
        print("2 1 3 4 ",b[2][5],'\n');
        print("3 1 2 4 ",b[3][5],'\n');
        print("4 1 2 3 ",b[4][5],'\n');
    } else if(n==5){
        for(int i=2;i<=n;i++)
            for(int j=1;j<i;j++){
                a[i][j]=a[j][i];
                tot+=a[i][j]&1;
            }
        solve(1),print("-1\n");
    } else{
        for(int i=2;i<=n;i++)
            for(int j=1;j<i;j++)
                a[i][j]=a[j][i];
        for(int i=1;i<=n;i++)
            for(int j=1;j<=n;j++){
                if(j==i) continue;
                int k=j+1;
                if(k==i) k++;
                if(k>n||!a[i][j])
                    continue;
                auto [x,y,z]=mex(i,j,k);
                ans.push_back({x,y,j,i,a[i][j]});
                ans.push_back({j,i,x,z,-a[i][j]});
                ans.push_back({j,i,y,z,a[i][j]});
                ans.push_back({x,y,k,i,-a[i][j]});
                ans.push_back({k,i,x,z,a[i][j]});
                ans.push_back({k,i,y,z,-a[i][j]});
                a[i][k]+=a[i][j];
                a[k][i]+=a[i][j];
                a[i][j]=a[j][i]=0;
            }
        print(ans.size(),'\n');
        for(auto tmp : ans)
            print(tmp.a,' ',tmp.b,' ',tmp.c,' ',tmp.d,' ',tmp.x,'\n');
    }
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 1ms
memory: 5888kb

input:

4
0 1 1
0 0
1
1 0 0
1 1
0

output:

4
1 2 3 4 0
2 1 3 4 1
3 1 2 4 0
4 1 2 3 0

result:

ok n=4

Test #2:

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

input:

4
3 3 3
0 0
0
0 0 0
3 3
3

output:

4
1 2 3 4 -3
2 1 3 4 0
3 1 2 4 0
4 1 2 3 0

result:

ok n=4

Test #3:

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

input:

5
-12 15 -12 1
37 14 7
7 9
-11
12 5 1 13
-1 -4 -7
-5 -9
18

output:

-1

result:

ok n=5

Test #4:

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

input:

4
37 81 -38
-79 -8
-42
20 -55 80
-23 -43
37

output:

-1

result:

ok n=4

Test #5:

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

input:

5
-22 63 -23 7
-11 36 66
66 -77
36
-87 -17 95 -65
-93 53 63
-54 -56
-77

output:

-1

result:

ok n=5

Test #6:

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

input:

6
-59 77 100 -28 -80
-14 -19 34 0
-8 34 44
58 38
7
87 -53 -57 -79 86
-19 -97 -51 -29
42 -14 61
-6 25
-24

output:

-1

result:

ok n=6

Test #7:

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

input:

10
96 -62 71 43 -41 62 37 -17 -73
-51 55 89 63 -17 81 98 78
-96 -70 -16 78 -63 49 86
20 -76 -21 8 -32 16
-93 45 -65 99 65
9 81 47 -2
-50 94 2
29 -77
77
67 -91 -97 -13 -75 -8 -79 21 -86
-44 -55 -92 19 -62 47 25 -88
-89 -10 1 94 -61 78 -70
8 30 -54 -9 19 -60
35 -21 -79 40 92
-56 -12 -56 2
-38 23 -31
2...

output:

-1

result:

ok n=10

Test #8:

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

input:

30
79 75 -71 -8 36 26 -38 -45 43 44 64 52 -23 -64 -73 97 -79 70 24 58 -9 11 14 58 -95 -88 -10 -80 -47
20 -55 86 89 -39 15 26 -32 38 -23 -30 -12 -4 81 39 -13 -43 -11 -38 -70 14 32 -67 -54 38 -80 -80 97
-49 -92 53 -94 -60 -77 -80 -11 75 51 43 52 -28 58 -26 71 -85 66 96 -61 52 -100 -49 93 92 -37 62
-55...

output:

-1

result:

ok n=30

Test #9:

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

input:

50
-47 49 10 46 -54 -70 -39 36 -1 100 -78 -27 23 43 15 -21 71 48 -82 95 85 -11 -99 35 -44 -31 70 -94 12 -45 -81 75 62 89 14 85 -82 -25 2 5 54 -25 -96 -30 -12 -70 13 -51 15
-48 -13 -53 49 19 -62 -15 -99 54 29 17 67 31 -58 80 -2 -97 -40 59 64 84 15 -32 76 -18 35 76 68 -69 47 51 -26 64 -70 71 14 -3 47 ...

output:

-1

result:

ok n=50

Test #10:

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

input:

100
-25 31 38 48 -19 32 87 -10 -30 -88 -79 98 -99 56 -52 -86 -89 51 77 -36 -52 72 -78 48 30 42 -45 84 -75 -71 -83 -48 92 -44 6 -83 -87 -82 -17 40 -44 82 64 -90 89 -34 88 10 -26 -84 -51 -29 86 -55 55 78 12 -38 -96 28 -78 52 -30 85 72 79 57 8 71 -68 -81 -21 14 44 -42 -26 42 95 20 -78 18 29 100 39 -19 ...

output:

-1

result:

ok n=100

Test #11:

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

input:

4
75 -69 93
78 24
-61
75 59 80
-50 31
-55

output:

-1

result:

ok n=4

Test #12:

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

input:

4
44 -25 -81
84 8
95
-70 -21 82
32 28
74

output:

-1

result:

ok n=4

Test #13:

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

input:

4
91 -18 -46
-80 -34
38
-25 18 -40
-35 86
-53

output:

-1

result:

ok n=4

Test #14:

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

input:

5
-16 92 -94 -83
-83 16 -74
75 3
-43
-28 45 -63 -100
-11 -39 -80
62 -14
21

output:

-1

result:

ok n=5

Test #15:

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

input:

5
-95 7 -3 76
57 -85 -98
-64 -28
70
5 48 -42 -99
-56 22 21
-51 74
-85

output:

-1

result:

ok n=5

Test #16:

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

input:

5
-10 31 33 -71
33 -49 4
72 -72
65
-74 55 20 41
61 62 -83
50 -1
-95

output:

-1

result:

ok n=5

Test #17:

score: -100
Wrong Answer
time: 1ms
memory: 5600kb

input:

6
65 -33 2 -67 83
40 93 -28 86
54 -30 -11
56 40
-66
82 42 -32 -56 98
1 85 17 45
-12 -3 -50
-39 6
100

output:

84
4 5 2 1 17
2 1 4 6 -17
2 1 5 6 17
4 5 3 1 -17
3 1 4 6 17
3 1 5 6 -17
2 5 3 1 92
3 1 2 6 -92
3 1 5 6 92
2 5 4 1 -92
4 1 2 6 92
4 1 5 6 -92
2 3 4 1 58
4 1 2 6 -58
4 1 3 6 58
2 3 5 1 -58
5 1 2 6 58
5 1 3 6 -58
2 3 5 1 69
5 1 2 4 -69
5 1 3 4 69
2 3 6 1 -69
6 1 2 4 69
6 1 3 4 -69
1 5 3 2 -39
3 2 1 6 3...

result:

wrong answer Wrong Answer!