QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#588446#6432. Puzzle in InazumaNianFengAC ✓2ms7748kbC++147.0kb2024-09-25 11:29:292024-09-25 11:43:22

Judging History

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

  • [2024-09-25 11:43:22]
  • 评测
  • 测评结果:AC
  • 用时:2ms
  • 内存:7748kb
  • [2024-09-25 11:29:29]
  • 提交

answer

#include <cassert>
#include <cstdio>
#include <string>
#include <vector>
#include <tuple>
#define i128 __int128
#define i64 long long
#define uit unsigned int
#define ull unsigned i64
#define tp3 tuple<int,int,int>
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];
int sum,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}
};
struct Answer{
    int a,b,c,d,x;
    void out(){
        print(a,' ',b,' ',c,' ',d,' ',x,'\n');
    }
};
vector<Answer>ans;
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;
}
tp3 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);
}
#define t(_) nod[tmp][_]
void dfs(int tmp){
    if(!tot){
        for(int i=1;i<=5;i++){
            if(!use[i]) continue;
            ans.push_back({
                nod[i][1],
                nod[i][2],
                nod[i][3],
                nod[i][4],
            1});
        }
        for(int i=1;i<=n;i++){
            for(int j=1;j<=n;j++){
                if(i==j||!a[i][j])
                    continue;
                int k=j+1==i?i+1:j+1;
                if(k>n) continue;
                auto [x,y,z]=mex(i,j,k);
                ans.push_back({x,i,y,j,-a[i][j]/2});
                ans.push_back({x,i,y,k,a[i][j]/2});
                ans.push_back({j,i,k,x,a[i][j]/2});
                ans.push_back({j,i,y,k,-a[i][j]/2});
                ans.push_back({y,i,x,j,-a[i][j]/2});
                ans.push_back({y,i,x,k,a[i][j]/2});
                ans.push_back({j,i,k,y,a[i][j]/2});
                ans.push_back({j,i,x,k,-a[i][j]/2});
                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 it : ans)
            it.out();
        exit(0);
    }
    if(tmp>5) return;
    dfs(tmp+1);
    use[tmp]=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;
        }
    }
    dfs(tmp+1);
    use[tmp]=false;
    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;
        }
    }
}
int main(){
    // file(qoj,);
    read(n);
    for(int i=1;i<=n;i++){
        for(int j=i+1;j<=n;j++){
            read(a[i][j]);
        }
    }
    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;
            }
        dfs(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(i==j||!a[i][j])
                    continue;
                int k=j+1==i?i+1:j+1;
                if(k>n) continue;
                auto [x,y,z]=mex(i,j,k);
                ans.push_back({x,i,y,j,-a[i][j]});
                ans.push_back({j,i,z,x,a[i][j]});
                ans.push_back({j,i,y,z,-a[i][j]});
                ans.push_back({x,i,y,k,a[i][j]});
                ans.push_back({k,i,z,x,-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 it : ans)
            it.out();
    }
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

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

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: 1ms
memory: 5604kb

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: 5604kb

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: 0ms
memory: 7748kb

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: 0ms
memory: 5612kb

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: 0ms
memory: 5668kb

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: 5708kb

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: 5848kb

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: 1ms
memory: 5856kb

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: 1ms
memory: 5684kb

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: 0ms
memory: 5672kb

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: 5604kb

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: 0ms
memory: 5668kb

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: 5868kb

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: 5636kb

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: 5900kb

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: 0
Accepted
time: 1ms
memory: 5868kb

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 1 5 2 -17
2 1 6 4 17
2 1 5 6 -17
4 1 5 3 17
3 1 6 4 -17
3 1 5 6 17
2 1 5 3 -92
3 1 6 2 92
3 1 5 6 -92
2 1 5 4 92
4 1 6 2 -92
4 1 5 6 92
2 1 3 4 -58
4 1 6 2 58
4 1 3 6 -58
2 1 3 5 58
5 1 6 2 -58
5 1 3 6 58
2 1 3 5 -69
5 1 4 2 69
5 1 3 4 -69
2 1 3 6 69
6 1 4 2 -69
6 1 3 4 69
1 2 5 3 39
3 2 6 1 -3...

result:

ok n=6

Test #18:

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

input:

10
-68 -48 27 80 89 -22 -43 34 43
-41 -4 -10 -90 -62 -11 83 22
-64 -77 84 -20 -56 -56 -79
49 -54 90 19 75 6
41 6 -33 -29 -39
45 -27 7 6
-57 93 -53
-46 -85
-37
40 -49 -32 -28 -16 -71 -97 -99 -67
6 34 -65 -97 95 -99 72 -34
81 32 16 -49 -71 61 -83
89 -23 2 35 -20 50
-14 32 83 31 -43
-15 74 -87 22
-56 -...

output:

264
4 1 5 2 -108
2 1 6 4 108
2 1 5 6 -108
4 1 5 3 108
3 1 6 4 -108
3 1 5 6 108
2 1 5 3 -107
3 1 6 2 107
3 1 5 6 -107
2 1 5 4 107
4 1 6 2 -107
4 1 5 6 107
2 1 3 4 -48
4 1 6 2 48
4 1 3 6 -48
2 1 3 5 48
5 1 6 2 -48
5 1 3 6 48
2 1 3 5 60
5 1 4 2 -60
5 1 3 4 60
2 1 3 6 -60
6 1 4 2 60
6 1 3 4 -60
2 1 3 6 ...

result:

ok n=10

Test #19:

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

input:

30
-14 20 -41 -72 25 -17 -90 -2 12 -45 -13 -43 78 -3 15 -25 -5 43 38 -59 -20 -25 29 0 18 -54 49 -13 -88
87 -6 -53 -40 -13 6 -50 -38 -73 -15 95 88 -48 86 96 -63 -2 -49 -85 -19 -44 -11 -94 -51 -68 -71 -40 9
-11 -35 73 6 -10 -67 39 37 6 -3 81 -39 -89 -49 38 17 -25 2 11 -100 22 52 -39 -24 8 -78 13
51 81...

output:

2598
4 1 5 2 46
2 1 6 4 -46
2 1 5 6 46
4 1 5 3 -46
3 1 6 4 46
3 1 5 6 -46
2 1 5 3 69
3 1 6 2 -69
3 1 5 6 69
2 1 5 4 -69
4 1 6 2 69
4 1 5 6 -69
2 1 3 4 63
4 1 6 2 -63
4 1 3 6 63
2 1 3 5 -63
5 1 6 2 63
5 1 3 6 -63
2 1 3 5 -34
5 1 4 2 34
5 1 3 4 -34
2 1 3 6 34
6 1 4 2 -34
6 1 3 4 34
2 1 3 6 -27
6 1 4 2...

result:

ok n=30

Test #20:

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

input:

50
-98 59 55 -73 49 29 73 -28 51 -81 77 88 -54 -2 58 6 17 -56 15 66 8 -86 96 -41 -33 93 84 4 -14 18 46 64 3 -73 -3 -65 49 30 35 -84 82 -66 93 83 -46 -42 95 -88 32
82 -2 -69 78 -69 -29 95 -25 -96 23 -78 -2 12 77 -79 65 13 17 69 14 91 82 43 -91 -25 6 8 17 -98 8 17 36 17 -80 91 -3 -35 -88 91 -89 80 25 ...

output:

7344
4 1 5 2 -17
2 1 6 4 17
2 1 5 6 -17
4 1 5 3 17
3 1 6 4 -17
3 1 5 6 17
2 1 5 3 59
3 1 6 2 -59
3 1 5 6 59
2 1 5 4 -59
4 1 6 2 59
4 1 5 6 -59
2 1 3 4 165
4 1 6 2 -165
4 1 3 6 165
2 1 3 5 -165
5 1 6 2 165
5 1 3 6 -165
2 1 3 5 161
5 1 4 2 -161
5 1 3 4 161
2 1 3 6 -161
6 1 4 2 161
6 1 3 4 -161
2 1 3 6...

result:

ok n=50

Test #21:

score: 0
Accepted
time: 2ms
memory: 6348kb

input:

100
-93 27 9 49 -69 -2 26 37 -10 -52 43 81 96 -10 32 46 -18 13 14 59 -58 3 -68 33 -62 -13 39 93 15 -81 -6 96 -81 -50 77 50 93 95 11 79 86 25 -28 48 77 5 -9 89 9 -62 86 -45 -50 70 -94 75 12 47 73 -26 -83 -29 -28 -70 -31 58 -67 63 47 9 -95 -52 94 -22 -96 -84 16 53 -14 -98 -11 26 -59 -28 -60 -80 -76 -2...

output:

29664
4 1 5 2 -147
2 1 6 4 147
2 1 5 6 -147
4 1 5 3 147
3 1 6 4 -147
3 1 5 6 147
2 1 5 3 -210
3 1 6 2 210
3 1 5 6 -210
2 1 5 4 210
4 1 6 2 -210
4 1 5 6 210
2 1 3 4 -290
4 1 6 2 290
4 1 3 6 -290
2 1 3 5 290
5 1 6 2 -290
5 1 3 6 290
2 1 3 5 -219
5 1 4 2 219
5 1 3 4 -219
2 1 3 6 219
6 1 4 2 -219
6 1 3 ...

result:

ok n=100

Test #22:

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

input:

4
63 -85 -96
73 -75
-24
-17 1 -24
-83 -8
-13

output:

-1

result:

ok n=4

Test #23:

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

input:

5
25 -22 24 37
-48 67 25
97 -55
57
-82 -44 -25 27
-35 89 81
88 37
71

output:

-1

result:

ok n=5

Test #24:

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

input:

6
-59 84 42 67 72
-51 -86 -37 -2
61 -84 -78
-8 -81
76
61 41 -3 32 -74
30 -39 -37 -13
-23 100 -24
-90 -41
-4

output:

84
4 1 5 2 -120
2 1 6 4 120
2 1 5 6 -120
4 1 5 3 120
3 1 6 4 -120
3 1 5 6 120
2 1 5 3 -77
3 1 6 2 77
3 1 5 6 -77
2 1 5 4 77
4 1 6 2 -77
4 1 5 6 77
2 1 3 4 -32
4 1 6 2 32
4 1 3 6 -32
2 1 3 5 32
5 1 6 2 -32
5 1 3 6 32
2 1 3 5 3
5 1 4 2 -3
5 1 3 4 3
2 1 3 6 -3
6 1 4 2 3
6 1 3 4 -3
1 2 5 3 -81
3 2 6 1 8...

result:

ok n=6

Test #25:

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

input:

7
98 -77 33 -59 44 21
-71 -78 42 82 -60
6 76 96 -18
53 96 1
-72 -53
-86
69 40 -13 -11 63 55
-70 86 -49 -29 -34
-4 -51 67 19
-81 1 70
-77 10
13

output:

120
4 1 5 2 29
2 1 6 4 -29
2 1 5 6 29
4 1 5 3 -29
3 1 6 4 29
3 1 5 6 -29
2 1 5 3 -88
3 1 6 2 88
3 1 5 6 -88
2 1 5 4 88
4 1 6 2 -88
4 1 5 6 88
2 1 3 4 -42
4 1 6 2 42
4 1 3 6 -42
2 1 3 5 42
5 1 6 2 -42
5 1 3 6 42
2 1 3 5 -90
5 1 4 2 90
5 1 3 4 -90
2 1 3 6 90
6 1 4 2 -90
6 1 3 4 90
2 1 3 6 -109
6 1 4 2...

result:

ok n=7

Test #26:

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

input:

37
1 -86 11 -63 -41 -21 99 14 28 17 63 66 24 53 2 -79 9 -95 -63 -40 12 -9 -71 90 -33 -13 -22 -36 50 31 -63 -1 7 -35 100 97
-57 -66 60 57 -30 8 32 -95 99 -67 -1 14 -75 83 42 -17 86 90 -33 -52 21 48 12 -69 -37 -25 74 -14 39 -20 65 38 14 -59 89
59 -3 91 76 -16 20 1 -85 51 -23 -24 49 10 -28 -11 -96 16 -...

output:

3984
4 1 5 2 84
2 1 6 4 -84
2 1 5 6 84
4 1 5 3 -84
3 1 6 4 84
3 1 5 6 -84
2 1 5 3 71
3 1 6 2 -71
3 1 5 6 71
2 1 5 4 -71
4 1 6 2 71
4 1 5 6 -71
2 1 3 4 70
4 1 6 2 -70
4 1 3 6 70
2 1 3 5 -70
5 1 6 2 70
5 1 3 6 -70
2 1 3 5 -34
5 1 4 2 34
5 1 3 4 -34
2 1 3 6 34
6 1 4 2 -34
6 1 3 4 34
2 1 3 6 -155
6 1 4 ...

result:

ok n=37

Test #27:

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

input:

71
100 39 36 -14 -71 -95 1 23 -66 -23 58 46 83 67 16 95 -77 21 -87 20 69 -50 -74 -69 90 75 -18 84 -45 63 63 51 34 58 -51 90 -91 -50 -89 58 3 63 56 -58 -51 16 72 -36 36 64 -67 38 42 -93 76 -51 0 21 58 37 -4 26 -22 -12 72 93 -98 51 -11 -47
95 95 -17 -51 67 -38 63 74 52 89 80 -94 37 -18 -73 -32 -94 17 ...

output:

14874
4 1 5 2 22
2 1 6 4 -22
2 1 5 6 22
4 1 5 3 -22
3 1 6 4 22
3 1 5 6 -22
2 1 5 3 -27
3 1 6 2 27
3 1 5 6 -27
2 1 5 4 27
4 1 6 2 -27
4 1 5 6 27
2 1 3 4 74
4 1 6 2 -74
4 1 3 6 74
2 1 3 5 -74
5 1 6 2 74
5 1 3 6 -74
2 1 3 5 -25
5 1 4 2 25
5 1 3 4 -25
2 1 3 6 25
6 1 4 2 -25
6 1 3 4 25
2 1 3 6 -120
6 1 4...

result:

ok n=71

Test #28:

score: 0
Accepted
time: 2ms
memory: 6312kb

input:

97
-73 49 60 15 -5 57 94 79 -7 51 -26 -21 -78 -67 31 90 7 46 -75 -82 3 24 -28 81 -77 -100 53 65 6 -63 17 100 13 -19 14 67 -31 7 92 45 61 58 -83 8 65 93 -35 94 97 97 80 -45 63 -15 57 -40 -65 -67 -32 12 -26 -99 32 -62 28 27 -25 52 -45 39 27 -34 78 65 -23 91 -71 -46 5 -36 84 -11 44 44 -74 -62 -91 -75 2...

output:

27888
4 1 5 2 -113
2 1 6 4 113
2 1 5 6 -113
4 1 5 3 113
3 1 6 4 -113
3 1 5 6 113
2 1 5 3 -28
3 1 6 2 28
3 1 5 6 -28
2 1 5 4 28
4 1 6 2 -28
4 1 5 6 28
2 1 3 4 100
4 1 6 2 -100
4 1 3 6 100
2 1 3 5 -100
5 1 6 2 100
5 1 3 6 -100
2 1 3 5 169
5 1 4 2 -169
5 1 3 4 169
2 1 3 6 -169
6 1 4 2 169
6 1 3 4 -169
...

result:

ok n=97

Test #29:

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

input:

59
-83 56 51 -64 30 35 52 -22 -54 -36 76 25 37 39 -26 -10 2 -99 71 95 -67 -2 33 9 -79 97 -18 -56 -54 99 -2 -3 -64 -42 -72 81 -84 5 -39 93 -72 -90 19 4 95 -30 28 -1 -81 -59 47 15 -94 -59 87 0 82 26
42 76 56 47 -5 26 -76 85 -16 -16 68 -19 26 -93 0 24 -47 20 16 -63 75 -36 -2 -88 38 -14 -70 27 -98 -70 4...

output:

10254
4 1 5 2 -154
2 1 6 4 154
2 1 5 6 -154
4 1 5 3 154
3 1 6 4 -154
3 1 5 6 154
2 1 5 3 -83
3 1 6 2 83
3 1 5 6 -83
2 1 5 4 83
4 1 6 2 -83
4 1 5 6 83
2 1 3 4 -55
4 1 6 2 55
4 1 3 6 -55
2 1 3 5 55
5 1 6 2 -55
5 1 3 6 55
2 1 3 5 -136
5 1 4 2 136
5 1 3 4 -136
2 1 3 6 136
6 1 4 2 -136
6 1 3 4 136
2 1 3 ...

result:

ok n=59

Test #30:

score: 0
Accepted
time: 2ms
memory: 6192kb

input:

100
33 54 -87 -27 79 -67 -64 29 -32 49 -43 87 29 -64 38 -27 47 -67 -57 -66 -84 -67 68 -34 -12 -50 -55 -75 -96 0 71 -49 46 -39 63 -48 -60 -53 -92 18 -33 51 1 47 -100 42 81 -40 -14 43 -51 -7 -77 30 -20 -93 -99 -70 26 52 -58 -74 57 -54 -3 93 58 -90 32 -100 -72 51 -93 48 19 84 -89 77 55 12 -45 -5 39 5 -...

output:

29646
4 1 5 2 -27
2 1 6 4 27
2 1 5 6 -27
4 1 5 3 27
3 1 6 4 -27
3 1 5 6 27
2 1 5 3 42
3 1 6 2 -42
3 1 5 6 42
2 1 5 4 -42
4 1 6 2 42
4 1 5 6 -42
2 1 3 4 -42
4 1 6 2 42
4 1 3 6 -42
2 1 3 5 42
5 1 6 2 -42
5 1 3 6 42
2 1 3 5 -52
5 1 4 2 52
5 1 3 4 -52
2 1 3 6 52
6 1 4 2 -52
6 1 3 4 52
2 1 3 6 17
6 1 4 2...

result:

ok n=100

Test #31:

score: 0
Accepted
time: 2ms
memory: 6440kb

input:

100
68 -49 44 23 8 57 17 32 21 46 43 -84 -62 63 -83 99 -63 59 -11 31 83 -62 -24 66 -50 81 30 -55 -7 -82 68 73 -31 -33 -65 -91 -70 -68 73 50 -87 86 58 14 8 -24 31 37 66 -46 38 -64 -79 13 15 88 -29 29 -84 0 -10 -75 -100 -26 -50 -38 36 -35 85 48 58 -98 5 63 40 -61 93 -52 -37 16 -6 72 -77 -83 -87 50 -20...

output:

29658
4 1 5 2 57
2 1 6 4 -57
2 1 5 6 57
4 1 5 3 -57
3 1 6 4 57
3 1 5 6 -57
2 1 5 3 -14
3 1 6 2 14
3 1 5 6 -14
2 1 5 4 14
4 1 6 2 -14
4 1 5 6 14
2 1 3 4 30
4 1 6 2 -30
4 1 3 6 30
2 1 3 5 -30
5 1 6 2 30
5 1 3 6 -30
2 1 3 5 -9
5 1 4 2 9
5 1 3 4 -9
2 1 3 6 9
6 1 4 2 -9
6 1 3 4 9
2 1 3 6 -49
6 1 4 2 49
6...

result:

ok n=100

Test #32:

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

input:

100
-54 27 -16 97 15 -92 -66 73 -13 12 44 -10 -47 95 -25 -67 21 73 -19 -7 96 1 98 66 -58 16 -49 26 9 -97 90 -58 -17 -26 69 1 -37 -40 33 -36 14 -74 -44 -83 -44 66 -52 -11 95 -66 46 -72 37 67 28 40 -63 37 -24 -29 24 28 41 2 -41 71 -29 25 26 93 59 11 -66 -60 70 24 -42 -65 79 -56 -24 77 23 51 -19 25 9 3...

output:

29646
4 1 5 2 -78
2 1 6 4 78
2 1 5 6 -78
4 1 5 3 78
3 1 6 4 -78
3 1 5 6 78
2 1 5 3 13
3 1 6 2 -13
3 1 5 6 13
2 1 5 4 -13
4 1 6 2 13
4 1 5 6 -13
2 1 3 4 97
4 1 6 2 -97
4 1 3 6 97
2 1 3 5 -97
5 1 6 2 97
5 1 3 6 -97
2 1 3 5 205
5 1 4 2 -205
5 1 3 4 205
2 1 3 6 -205
6 1 4 2 205
6 1 3 4 -205
2 1 3 6 232
...

result:

ok n=100

Test #33:

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

input:

5
96 70 0 -25
3 10 -61
-40 8
58
62 43 24 82
-81 -49 68
88 -20
-98

output:

-1

result:

ok n=5

Test #34:

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

input:

5
43 -6 -77 19
84 1 -9
-87 67
-68
-42 -48 77 65
17 -1 -86
-22 -42
49

output:

-1

result:

ok n=5

Test #35:

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

input:

5
-85 -81 -99 97
10 -58 -26
-7 48
1
71 -68 -86 -65
84 41 -74
-84 41
-60

output:

-1

result:

ok n=5

Test #36:

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

input:

5
-59 -76 -34 15
-16 76 -35
82 -35
-41
-70 -91 31 82
94 -50 -1
8 -37
-89

output:

76
1 3 4 5 1
1 2 4 5 1
1 2 3 5 1
1 2 3 4 1
4 1 5 2 7
4 1 5 3 -7
2 1 3 4 -7
2 1 5 3 7
5 1 4 2 7
5 1 4 3 -7
2 1 3 5 -7
2 1 4 3 7
2 1 5 3 16
2 1 5 4 -16
3 1 4 2 -16
3 1 5 4 16
5 1 2 3 16
5 1 2 4 -16
3 1 4 5 -16
3 1 2 4 16
2 1 3 4 -15
2 1 3 5 15
4 1 5 2 15
4 1 3 5 -15
3 1 2 4 -15
3 1 2 5 15
4 1 5 3 15
4...

result:

ok n=5

Test #37:

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

input:

4
-52 -78 -9
100 30
51
14 62 -52
86 -86
18

output:

-1

result:

ok n=4

Test #38:

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

input:

4
-74 73 69
-54 -65
44
59 -50 -46
32 -49
47

output:

-1

result:

ok n=4

Test #39:

score: 0
Accepted
time: 2ms
memory: 6308kb

input:

100
-61 -13 42 41 82 78 99 70 15 -38 76 -21 80 27 9 33 77 -15 -58 -80 -32 -8 52 -53 56 -86 -79 19 -26 -74 68 -92 61 9 2 -65 -92 47 -81 53 65 92 27 -84 94 -78 29 -61 27 68 91 -18 -95 64 67 -73 77 23 -77 -87 84 66 -84 -14 27 -64 -27 -74 -65 74 -65 69 -23 -75 -70 -77 -26 61 -23 47 -20 -5 1 -1 38 97 26 ...

output:

29646
4 1 5 2 -37
2 1 6 4 37
2 1 5 6 -37
4 1 5 3 37
3 1 6 4 -37
3 1 5 6 37
2 1 5 3 -95
3 1 6 2 95
3 1 5 6 -95
2 1 5 4 95
4 1 6 2 -95
4 1 5 6 95
2 1 3 4 3
4 1 6 2 -3
4 1 3 6 3
2 1 3 5 -3
5 1 6 2 3
5 1 3 6 -3
2 1 3 5 -10
5 1 4 2 10
5 1 3 4 -10
2 1 3 6 10
6 1 4 2 -10
6 1 3 4 10
2 1 3 6 107
6 1 4 2 -107...

result:

ok n=100

Test #40:

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

input:

100
-80 84 40 30 -73 76 -79 9 32 -61 86 -44 13 -8 -97 -85 -9 76 75 85 -2 -22 25 58 -37 4 -86 64 -89 25 14 32 11 -71 -62 -55 -78 19 -54 -2 12 56 -78 33 74 1 -98 -1 -41 19 71 0 24 -5 -59 -92 78 62 -84 59 75 95 -27 22 -88 77 50 80 25 -77 29 -28 -34 -98 81 43 -91 -31 21 100 31 -96 -5 -51 -1 80 -23 9 15 ...

output:

29658
4 1 5 2 -7
2 1 6 4 7
2 1 5 6 -7
4 1 5 3 7
3 1 6 4 -7
3 1 5 6 7
2 1 5 3 155
3 1 6 2 -155
3 1 5 6 155
2 1 5 4 -155
4 1 6 2 155
4 1 5 6 -155
2 1 3 4 198
4 1 6 2 -198
4 1 3 6 198
2 1 3 5 -198
5 1 6 2 198
5 1 3 6 -198
2 1 3 5 293
5 1 4 2 -293
5 1 3 4 293
2 1 3 6 -293
6 1 4 2 293
6 1 3 4 -293
2 1 3 ...

result:

ok n=100

Test #41:

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

input:

4
40 -37 6
-68 -33
100
43 28 9
-71 -98
97

output:

4
1 2 3 4 34
2 1 3 4 0
3 1 2 4 31
4 1 2 3 0

result:

ok n=4

Test #42:

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

input:

4
84 -41 68
30 -18
19
73 -64 21
77 5
30

output:

4
1 2 3 4 -17
2 1 3 4 18
3 1 2 4 12
4 1 2 3 0

result:

ok n=4

Test #43:

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

input:

4
27 -78 29
81 -14
-44
41 -62 33
77 -30
-58

output:

4
1 2 3 4 15
2 1 3 4 5
3 1 2 4 6
4 1 2 3 0

result:

ok n=4

Test #44:

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

input:

4
-82 85 8
1 -50
-10
-41 50 47
-38 -15
-51

output:

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

result:

ok n=4

Test #45:

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

input:

4
-39 -81 59
-49 52
-66
-32 -74 24
-14 45
-73

output:

4
1 2 3 4 7
2 1 3 4 21
3 1 2 4 21
4 1 2 3 0

result:

ok n=4

Test #46:

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

input:

4
6 6 6
6 6
6
2 2 2
2 2
2

output:

-1

result:

ok n=4

Test #47:

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

input:

5
6 6 6 6
6 6 6
6 6
6
2 2 2 2
2 2 2
2 2
2

output:

-1

result:

ok n=5

Test #48:

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

input:

5
-21 -29 -2 -46
-55 78 43
87 -33
18
-55 55 -78 -8
-38 -25 60
50 16
63

output:

73
2 3 4 5 1
4 1 5 2 17
4 1 5 3 -17
2 1 3 4 -17
2 1 5 3 17
5 1 4 2 17
5 1 4 3 -17
2 1 3 5 -17
2 1 4 3 17
2 1 5 3 -25
2 1 5 4 25
3 1 4 2 25
3 1 5 4 -25
5 1 2 3 -25
5 1 2 4 25
3 1 4 5 25
3 1 2 4 -25
2 1 3 4 13
2 1 3 5 -13
4 1 5 2 -13
4 1 3 5 13
3 1 2 4 13
3 1 2 5 -13
4 1 5 3 -13
4 1 2 5 13
1 2 5 3 -8
...

result:

ok n=5

Test #49:

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

input:

5
95 -11 -61 61
85 -32 -14
-12 -75
-89
-42 -14 -23 40
-79 91 -90
19 -19
64

output:

74
2 3 4 5 1
1 2 3 5 1
4 1 5 2 69
4 1 5 3 -69
2 1 3 4 -69
2 1 5 3 69
5 1 4 2 69
5 1 4 3 -69
2 1 3 5 -69
2 1 4 3 69
2 1 5 3 71
2 1 5 4 -71
3 1 4 2 -71
3 1 5 4 71
5 1 2 3 71
5 1 2 4 -71
3 1 4 5 -71
3 1 2 4 71
2 1 3 4 52
2 1 3 5 -52
4 1 5 2 -52
4 1 3 5 52
3 1 2 4 52
3 1 2 5 -52
4 1 5 3 -52
4 1 2 5 52
1...

result:

ok n=5

Test #50:

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

input:

5
30 12 46 66
-22 -53 -8
63 -40
-84
36 38 36 55
-63 -22 2
28 -4
-96

output:

75
1 3 4 5 1
1 2 4 5 1
1 2 3 5 1
4 1 5 2 -2
4 1 5 3 2
2 1 3 4 2
2 1 5 3 -2
5 1 4 2 -2
5 1 4 3 2
2 1 3 5 2
2 1 4 3 -2
2 1 5 3 -14
2 1 5 4 14
3 1 4 2 14
3 1 5 4 -14
5 1 2 3 -14
5 1 2 4 14
3 1 4 5 14
3 1 2 4 -14
2 1 3 4 -8
2 1 3 5 8
4 1 5 2 8
4 1 3 5 -8
3 1 2 4 -8
3 1 2 5 8
4 1 5 3 8
4 1 2 5 -8
1 2 5 3...

result:

ok n=5

Test #51:

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

input:

5
-89 -74 46 -19
59 46 45
-15 -35
-12
-35 -87 -5 28
15 76 37
-22 -56
1

output:

73
1 3 4 5 1
4 1 5 2 -27
4 1 5 3 27
2 1 3 4 27
2 1 5 3 -27
5 1 4 2 -27
5 1 4 3 27
2 1 3 5 27
2 1 4 3 -27
2 1 5 3 -20
2 1 5 4 20
3 1 4 2 20
3 1 5 4 -20
5 1 2 3 -20
5 1 2 4 20
3 1 4 5 20
3 1 2 4 -20
2 1 3 4 6
2 1 3 5 -6
4 1 5 2 -6
4 1 3 5 6
3 1 2 4 6
3 1 2 5 -6
4 1 5 3 -6
4 1 2 5 6
1 2 5 3 22
1 2 5 4 ...

result:

ok n=5

Test #52:

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

input:

5
-91 -64 -43 -21
-48 11 -46
-58 43
-43
-52 -87 -45 -79
-35 57 -58
-18 -5
-38

output:

75
2 3 4 5 1
1 3 4 5 1
1 2 4 5 1
4 1 5 2 -19
4 1 5 3 19
2 1 3 4 19
2 1 5 3 -19
5 1 4 2 -19
5 1 4 3 19
2 1 3 5 19
2 1 4 3 -19
2 1 5 3 -7
2 1 5 4 7
3 1 4 2 7
3 1 5 4 -7
5 1 2 3 -7
5 1 2 4 7
3 1 4 5 7
3 1 2 4 -7
2 1 3 4 -5
2 1 3 5 5
4 1 5 2 5
4 1 3 5 -5
3 1 2 4 -5
3 1 2 5 5
4 1 5 3 5
4 1 2 5 -5
1 2 5 3...

result:

ok n=5

Test #53:

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

input:

5
-18 70 -27 11
54 -19 36
-94 85
-52
9 41 -28 35
-3 -12 36
-39 75
-68

output:

73
1 2 3 4 1
4 1 5 2 -13
4 1 5 3 13
2 1 3 4 13
2 1 5 3 -13
5 1 4 2 -13
5 1 4 3 13
2 1 3 5 13
2 1 4 3 -13
2 1 5 3 2
2 1 5 4 -2
3 1 4 2 -2
3 1 5 4 2
5 1 2 3 2
5 1 2 4 -2
3 1 4 5 -2
3 1 2 4 2
2 1 3 4 3
2 1 3 5 -3
4 1 5 2 -3
4 1 3 5 3
3 1 2 4 3
3 1 2 5 -3
4 1 5 3 -3
4 1 2 5 3
1 2 5 3 28
1 2 5 4 -28
3 2 ...

result:

ok n=5

Test #54:

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

input:

5
30 69 -94 16
75 32 49
59 31
26
71 26 -82 13
26 80 18
89 30
22

output:

65
1 2 3 5 1
4 1 5 2 -20
4 1 5 3 20
2 1 3 4 20
2 1 5 3 -20
5 1 4 2 -20
5 1 4 3 20
2 1 3 5 20
2 1 4 3 -20
2 1 5 3 2
2 1 5 4 -2
3 1 4 2 -2
3 1 5 4 2
5 1 2 3 2
5 1 2 4 -2
3 1 4 5 -2
3 1 2 4 2
2 1 3 4 -4
2 1 3 5 4
4 1 5 2 4
4 1 3 5 -4
3 1 2 4 -4
3 1 2 5 4
4 1 5 3 4
4 1 2 5 -4
1 2 5 3 24
1 2 5 4 -24
3 2 ...

result:

ok n=5

Test #55:

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

input:

5
84 -23 38 82
-1 3 32
-72 -40
-95
98 -5 -13 87
34 -25 38
-60 -100
-46

output:

75
2 3 4 5 1
1 2 3 5 1
1 2 3 4 1
4 1 5 2 -6
4 1 5 3 6
2 1 3 4 6
2 1 5 3 -6
5 1 4 2 -6
5 1 4 3 6
2 1 3 5 6
2 1 4 3 -6
2 1 5 3 -14
2 1 5 4 14
3 1 4 2 14
3 1 5 4 -14
5 1 2 3 -14
5 1 2 4 14
3 1 4 5 14
3 1 2 4 -14
2 1 3 4 12
2 1 3 5 -12
4 1 5 2 -12
4 1 3 5 12
3 1 2 4 12
3 1 2 5 -12
4 1 5 3 -12
4 1 2 5 12...

result:

ok n=5

Test #56:

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

input:

5
-56 48 23 92
-37 53 -18
-30 -28
-34
-57 99 0 89
-68 64 19
-85 -19
-29

output:

77
2 3 4 5 1
1 3 4 5 1
1 2 4 5 1
1 2 3 5 1
1 2 3 4 1
4 1 5 2 2
4 1 5 3 -2
2 1 3 4 -2
2 1 5 3 2
5 1 4 2 2
5 1 4 3 -2
2 1 3 5 -2
2 1 4 3 2
2 1 5 3 -22
2 1 5 4 22
3 1 4 2 22
3 1 5 4 -22
5 1 2 3 -22
5 1 2 4 22
3 1 4 5 22
3 1 2 4 -22
2 1 3 4 -9
2 1 3 5 9
4 1 5 2 9
4 1 3 5 -9
3 1 2 4 -9
3 1 2 5 9
4 1 5 3 ...

result:

ok n=5

Test #57:

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

input:

4
0 0 0
0 0
0
0 0 0
0 0
0

output:

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

result:

ok n=4