QOJ.ac
QOJ
The 2nd Universal Cup Finals is coming! Check out our event page, schedule, and competition rules!
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#828097 | #1845. Permute | Zi_Gao | WA | 264ms | 11664kb | C++20 | 2.2kb | 2024-12-23 13:18:38 | 2024-12-23 13:18:40 |
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];
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