QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#828039 | #1845. Permute | Zi_Gao | TL | 211ms | 5428kb | C++20 | 2.8kb | 2024-12-23 12:36:35 | 2024-12-23 12:36:35 |
Judging History
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...