QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#828039#1845. PermuteZi_GaoTL 211ms5428kbC++202.8kb2024-12-23 12:36:352024-12-23 12:36:35

Judging History

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

  • [2024-12-23 12:36:35]
  • 评测
  • 测评结果:TL
  • 用时:211ms
  • 内存:5428kb
  • [2024-12-23 12:36:35]
  • 提交

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];
std::map<u64,std::vector<NODE>> to[7];

u64 gethash(const std::vector<i64> &vec){
    register u64 hash=0;
    for(auto v:vec) hash=hash*121+v;
    return hash;
}

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

bool dfs(std::vector<i64> vec,int val){
    int vv=val;
    u64 vvec=gethash(vec);
    register int i=0;
    register i64 sum=0;
    for(i=0;i<7;++i) sum+=vec[i];
    if(!sum) return val==0;
    
    auto it=to[vv].find(vvec);
    if(it!=to[vv].end()) return !it->second.empty();

    std::vector<NODE> res;

    for(i=0;i<7;++i) if(vec[i]==sum){
        val=add(val,i,vec[i]);
        if(!val) res.push_back({vec[i],i});
        goto loop;
    }

    for(i=0;i<7;++i) if(vec[i]>5){
        res.push_back({vec[i]-5,i});
        val=add(val,i,vec[i]-5);
        vec[i]=5;
    }

    for(i=0;i<7;++i) if(vec[i]){
        vec[i]-=1;
        if(dfs(vec,(val*10+i)%7)==true){
            res.push_back({1ll,i});
            break;
        }
        vec[i]+=1;
    }
    if(i==8) i=-1;
    loop:;
    to[vv][vvec]=res;
    return !res.empty();
}

void solve(){
    register int i,val=0,vv;
    register i64 sum,min;
    for(i=0;i<10;++i) c[i]=read();
    for(i=7;i<10;++i) c[i%7]+=c[i];
    std::vector<i64> vec(c,c+7);
    if(!dfs(vec,0)) return puts("-1"),void();

    std::vector<NODE> res,tmp;
    sum=0;
    for(i=0;i<7;++i) sum+=vec[i];
    while(sum){
        vv=val;
        u64 vvec=gethash(vec);
        for(auto [len,k]:to[vv][vvec]){
            res.push_back({len,k});
            vec[k]-=len;
            sum-=len;
            val=add(val,k,len);
        }
    }

    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

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

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: 86ms
memory: 4152kb

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: 211ms
memory: 5428kb

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: -100
Time Limit Exceeded

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
13
1 7
1 0
1 0
1 0
1 8
1 8
1 8
1 1
1 1
1 9
1 5
1 5
2 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 5
1...

result: