QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#828097#1845. PermuteZi_GaoWA 264ms11664kbC++202.2kb2024-12-23 13:18:382024-12-23 13:18:40

Judging History

This is the latest submission verdict.

  • [2024-12-23 13:18:40]
  • Judged
  • Verdict: WA
  • Time: 264ms
  • Memory: 11664kb
  • [2024-12-23 13:18:38]
  • Submitted

answer

#include<bits/stdc++.h>

using i64=long long;
using u64=unsigned long long;

// #define ONLINE_JUDGE
#define INPUT_DATA_TYPE int
#define OUTPUT_DATA_TYPE int
inline __attribute((always_inline)) INPUT_DATA_TYPE read(){register INPUT_DATA_TYPE x=0;register char f=0,c=getchar();while(c<'0'||'9'<c)f=(c=='-'),c=getchar();while('0'<=c&&c<='9')x=(x<<3)+(x<<1)+(c&15),c=getchar();return f?-x:x;}void print(OUTPUT_DATA_TYPE x){if(x<0)x=-x,putchar('-');if(x>9)print(x/10);putchar(x%10^48);return;}

struct NODE{
    i64 len;
    int val;
};

i64 c[10];
int to[279936][7],pw[7];

int add(int val,int k,u64 len){
    int left=len%6;
    len-=left;
    while(left--)
        val=(val*10+k)%7;
    val=(val+(len/6)*11111*k)%7;
    return val;
}

void solve(){
    register int i,val=0,vv,s=0;
    for(i=0;i<10;++i) c[i]=read();
    for(i=7;i<10;++i) c[i-7]+=c[i];

    std::vector<NODE> res,tmp;

    for(i=6;~i;--i){
        if(c[i]>5) val=add(val,i,c[i]-5),res.push_back({c[i]-5,i}),c[i]=5;
        s=s*6+c[i];
    }
    if(to[s][val]==-1) return puts("-1"),void();

    while(s){
        res.push_back({1,to[s][val]});
        std::tie(val,s)=std::make_tuple((val*10+to[s][val])%7,s-pw[to[s][val]]);
    }

    for(auto [len,k]:res){
        if(k<=2&&c[k+7]){
            if(len<=c[k+7]) c[k+7]-=len,tmp.push_back({len,k+7});
            else tmp.push_back({c[k+7],k+7}),tmp.push_back({len-c[k+7],k}),c[k+7]=0;
        }else tmp.push_back({len,k});
    }

    printf("%d\n",tmp.size());
    for(auto [len,val]:tmp) printf("%lld %d\n",len,val);
}

int main(){
	#ifndef ONLINE_JUDGE
	freopen("name.in", "r", stdin);
	freopen("name.out", "w", stdout);
	#endif

    memset(to,-1,sizeof(to));
    register int i=0,j,s,maxs=279936;

    to[0][0]=1;

    for(i=pw[0]=1;i<7;++i) pw[i]=pw[i-1]*6;

    for(s=1;s<maxs;++s){
        c[0]+=1;
        for(i=0;i<7;++i){
            if(c[i]==6) c[i+1]+=1,c[i]=0;
            if(c[i]) for(j=0;j<7;++j)if(to[s][j]==-1&&to[s-pw[i]][(j*10+i)%7]!=-1)
                to[s][j]=i;
        }
    }

    int T=read();
    while(T--) solve();

	#ifndef ONLINE_JUDGE
	fclose(stdin);
	fclose(stdout);
	#endif
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 15ms
memory: 11480kb

input:

3
0 1 0 0 1 0 0 0 0 0
0 2 0 0 0 0 1 0 0 1
0 1000000000 0 0 0 0 0 0 0 0

output:

2
1 1
1 4
4
1 1
1 1
1 6
1 9
-1

result:

ok T=3

Test #2:

score: 0
Accepted
time: 70ms
memory: 11436kb

input:

100000
0 0 0 1 0 1 1 1 0 1
1 1 0 0 1 0 1 0 1 0
1 1 1 1 0 0 0 1 0 1
0 1 1 0 0 1 1 1 1 0
0 0 1 0 1 0 1 0 1 0
0 1 0 0 0 0 0 1 0 0
1 1 0 0 0 0 0 0 1 1
1 0 1 1 1 0 1 0 0 0
0 1 1 0 0 1 0 1 0 1
1 0 0 1 1 0 0 1 0 0
1 1 0 1 0 0 1 0 1 1
0 0 1 0 0 0 0 1 0 0
0 1 1 1 1 1 1 1 0 1
1 0 0 0 0 1 0 0 0 1
0 0 0 0 1 0 1...

output:

5
1 7
1 9
1 6
1 5
1 3
5
1 0
1 4
1 8
1 1
1 6
6
1 7
1 0
1 1
1 9
1 3
1 2
6
1 7
1 8
1 1
1 2
1 5
1 6
4
1 8
1 2
1 4
1 6
-1
4
1 0
1 8
1 1
1 9
5
1 0
1 2
1 4
1 3
1 6
5
1 7
1 1
1 9
1 2
1 5
-1
6
1 0
1 8
1 1
1 9
1 6
1 3
-1
8
1 7
1 1
1 9
1 2
1 4
1 3
1 5
1 6
-1
4
1 8
1 9
1 4
1 6
7
1 7
1 0
1 9
1 2
1 5
1 6
1 8
6
1 ...

result:

ok T=100000

Test #3:

score: 0
Accepted
time: 115ms
memory: 11640kb

input:

100000
2 1 2 1 0 1 1 0 2 0
1 2 0 1 1 2 1 1 2 1
2 2 2 1 0 2 1 1 2 2
1 1 0 2 0 2 0 1 2 0
1 0 2 2 1 2 1 0 2 2
0 1 2 2 2 1 0 2 1 2
1 1 2 0 0 1 1 0 1 0
1 0 2 2 2 0 1 0 1 1
2 1 1 2 1 0 2 0 0 1
1 0 2 2 2 0 2 1 0 1
2 0 1 1 1 1 1 1 2 1
0 1 1 0 2 0 2 0 1 2
2 1 1 0 2 0 2 1 0 1
1 2 2 2 0 2 1 1 1 0
2 0 0 2 0 2 2...

output:

10
1 0
1 0
1 8
1 8
1 1
1 2
1 2
1 3
1 5
1 6
12
1 7
1 0
1 8
1 8
1 1
1 1
1 9
1 3
1 4
1 5
1 6
1 5
15
1 7
1 0
1 0
1 8
1 8
1 1
1 1
1 9
1 9
1 2
1 2
1 5
1 5
1 3
1 6
9
1 7
1 0
1 8
1 8
1 1
1 3
1 5
1 5
1 3
13
1 0
1 8
1 8
1 9
1 9
1 2
1 2
1 3
1 3
1 5
1 4
1 5
1 6
13
1 7
1 7
1 8
1 1
1 9
1 9
1 2
1 2
1 3
1 4
1 3
1 4...

result:

ok T=100000

Test #4:

score: 0
Accepted
time: 160ms
memory: 11444kb

input:

100000
1 3 3 2 3 0 2 1 3 2
3 1 2 0 0 3 1 0 0 1
3 2 0 2 0 2 0 1 3 1
0 1 0 3 1 1 0 3 0 2
2 2 2 3 3 3 1 0 3 0
0 3 0 2 0 3 2 0 2 3
3 0 1 1 3 3 2 1 3 1
1 2 3 0 1 2 2 0 2 3
3 1 0 3 2 0 2 3 1 0
2 1 2 3 0 2 2 3 1 2
3 3 0 3 0 0 1 1 1 1
1 3 1 0 2 1 0 3 3 3
3 0 0 3 3 2 3 3 2 1
3 3 3 1 0 2 3 0 2 3
3 3 1 3 3 2 3...

output:

20
1 8
1 7
1 0
1 8
1 8
1 1
1 1
1 1
1 9
1 9
1 2
1 2
1 2
1 3
1 3
1 4
1 4
1 6
1 4
1 6
11
1 0
1 0
1 0
1 1
1 9
1 2
1 2
1 5
1 5
1 5
1 6
14
1 7
1 0
1 0
1 0
1 8
1 8
1 8
1 1
1 1
1 9
1 5
1 5
1 3
1 3
11
1 7
1 7
1 7
1 1
1 9
1 9
1 3
1 3
1 3
1 5
1 4
19
1 0
1 0
1 8
1 8
1 8
1 1
1 1
1 2
1 2
1 3
1 3
1 3
1 4
1 4
1 4
1...

result:

ok T=100000

Test #5:

score: 0
Accepted
time: 200ms
memory: 11636kb

input:

100000
0 1 3 1 1 0 1 3 0 1
4 3 4 1 3 4 3 4 2 3
1 3 1 3 3 4 3 4 2 2
1 0 1 0 3 3 3 1 1 1
3 4 1 3 1 0 1 2 1 2
0 1 2 1 4 1 0 3 4 2
0 4 1 2 4 3 2 1 1 3
0 4 0 4 2 1 0 2 1 3
4 4 0 4 4 1 4 1 4 1
1 3 2 1 1 4 2 3 4 1
3 3 4 3 3 4 1 2 1 4
3 1 4 0 3 0 4 3 1 4
3 0 3 2 3 4 2 3 1 3
3 1 2 4 3 4 2 4 1 1
2 1 0 2 2 3 2...

output:

11
1 7
1 7
1 7
1 1
1 9
1 2
1 2
1 2
1 3
1 6
1 4
28
2 9
3 7
1 7
1 0
1 0
1 0
1 0
1 8
1 8
1 1
1 1
1 1
1 9
1 2
1 2
1 2
1 2
1 3
1 4
1 4
1 4
1 5
1 5
1 5
1 6
1 6
1 6
1 5
26
1 7
1 7
1 7
1 7
1 0
1 8
1 8
1 1
1 1
1 1
1 9
1 9
1 2
1 3
1 3
1 3
1 4
1 4
1 4
1 5
1 5
1 5
1 6
1 5
1 6
1 6
14
1 7
1 0
1 8
1 9
1 2
1 4
1 4
...

result:

ok T=100000

Test #6:

score: 0
Accepted
time: 231ms
memory: 11616kb

input:

100000
0 2 1 4 1 4 1 1 3 4
2 3 3 1 3 4 2 1 1 1
1 2 1 3 3 1 1 5 0 0
1 4 0 3 1 1 0 0 0 4
4 3 5 0 0 0 4 2 5 1
3 2 5 1 2 5 0 0 0 1
2 0 5 3 1 3 0 5 1 3
0 2 5 4 5 5 1 1 1 0
1 3 1 4 4 5 2 2 2 1
2 1 2 1 0 0 1 2 5 1
0 2 0 4 5 4 5 2 0 3
5 3 5 5 2 2 4 0 5 5
3 4 2 2 5 1 5 0 3 4
0 3 3 0 5 3 3 4 3 5
0 3 5 4 3 3 4...

output:

21
1 7
1 8
1 8
1 8
1 1
1 1
1 9
1 9
1 9
1 9
1 2
1 3
1 3
1 3
1 3
1 4
1 6
1 5
1 5
1 5
1 5
21
1 7
1 0
1 0
1 8
1 1
1 1
1 1
1 9
1 2
1 2
1 2
1 3
1 4
1 4
1 4
1 5
1 6
1 5
1 6
1 5
1 5
17
1 7
1 7
1 7
1 7
1 7
1 0
1 1
1 1
1 2
1 3
1 3
1 3
1 4
1 4
1 4
1 6
1 5
14
1 0
1 1
1 1
1 1
1 1
1 9
1 9
1 9
1 9
1 3
1 3
1 3
1 4
...

result:

ok T=100000

Test #7:

score: -100
Wrong Answer
time: 264ms
memory: 11664kb

input:

100000
5 5 0 1 0 3 1 5 3 6
0 5 1 4 2 1 1 5 3 4
1 3 0 5 0 2 4 1 5 5
4 5 4 5 3 5 6 3 1 3
6 0 5 3 3 6 3 5 6 3
6 3 4 4 4 0 0 1 6 3
0 5 2 4 2 4 2 5 3 3
2 4 4 5 1 0 5 6 2 3
3 0 3 5 4 3 3 5 2 6
6 3 6 2 0 5 0 2 2 4
5 3 6 2 2 5 6 4 4 2
0 6 4 3 3 6 0 3 4 4
6 5 1 1 2 6 3 6 5 4
1 3 6 5 0 3 0 1 3 2
6 4 5 2 2 6 1...

output:

23
1 9
3 8
5 7
1 0
1 0
1 0
1 0
1 0
1 1
1 1
1 1
1 1
1 1
1 9
1 9
1 9
1 9
1 9
1 5
1 5
1 3
1 6
1 5
24
3 8
1 7
1 7
1 7
1 7
1 7
1 1
1 1
1 1
1 1
1 1
1 9
1 9
1 9
1 9
1 2
1 3
1 3
1 3
1 4
1 3
1 5
1 4
1 6
24
3 8
1 7
1 0
1 8
1 8
1 1
1 1
1 1
1 9
1 9
1 9
1 9
1 9
1 3
1 3
1 3
1 3
1 3
1 5
1 6
1 6
1 6
1 5
1 6
37
1 6
...

result:

wrong answer Participant output sum mod 7 = 2 in test 18