QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#129623 | #6300. Best Carry Player 2 | qL | WA | 2ms | 5620kb | C++14 | 8.3kb | 2023-07-22 21:29:52 | 2023-07-22 21:29:53 |
Judging History
answer
#include<cstdio>
#include<iostream>
#include<initializer_list>
namespace QL{
namespace details{
template<typename _Tp>
static constexpr std::size_t integral_length=sizeof(_Tp)*10/sizeof(int);
#ifndef _GLIBCXX_TYPE_TRAITS
template<typename _Tp>
struct is_unsigned{constexpr operator bool(){return false;}};
template<>
struct is_unsigned<unsigned int>{constexpr operator bool(){return true;}};
template<>
struct is_unsigned<unsigned long>{constexpr operator bool(){return true;}};
template<>
struct is_unsigned<unsigned long long>{constexpr operator bool(){return true;}};
template<>
struct is_unsigned<unsigned __int128>{constexpr operator bool(){return true;}};
template<>
struct is_unsigned<unsigned char>{constexpr operator bool(){return true;}};
template<typename _Tp>
static constexpr bool is_unsigned_t=is_unsigned<_Tp>();
#else
template<typename _Tp>
static constexpr bool is_unsigned_t=std::is_unsigned<_Tp>();
#endif
}
namespace IO{
using details::integral_length;
using details::is_unsigned_t;
class IO{
protected:
#ifdef _INITIALIZER_LIST
using LIST=std::initializer_list<int>;
#endif
#ifndef LOCAL
FILE*IN;
FILE*OUT;
static constexpr int SIZE=1<<20;
char buf[SIZE]{},*p1{},*p2{},obuf[SIZE]{},*p3{};
char std_getchar(){return p1==p2&&(p2=(p1=buf)+fread(buf,1,SIZE,IN),p1==p2)?EOF:*p1++;}
void std_putchar(char ch){(p3-obuf<SIZE)?(*p3++=ch):(out_end(),*p3++=ch);}
template<std::size_t L>
FILE*set_in(const char(&name)[L]){
static char in[L+5]={};
__builtin_memcpy(in,name,sizeof in);
in[L-1]='.',in[L]='i',in[L+1]='n',in[L+2]='\0';
return std::fopen(in,"r");
}
template<std::size_t L>
FILE*set_out(const char(&name)[L]){
static char out[L+5];
__builtin_memcpy(out,name,sizeof out);
out[L-1]='.',out[L]='o',out[L+1]='u',out[L+2]='t',out[L+3]='\0';
return std::fopen(out,"w");
}
#else
char std_getchar(){return std::getchar();}
void std_putchar(char ch){std::putchar(ch);}
void err_putchar(char ch){std::fprintf(stderr,"%c",ch);}
template<std::size_t L>
void reset_stdin(const char(&name)[L]){
static char in[L+5]={};
__builtin_memcpy(in,name,sizeof in);
in[L-1]='.',in[L]='i',in[L+1]='n',in[L+2]='\0';
freopen(in,"r",stdin);
}
template<std::size_t L>
void reset_stdout(const char(&name)[L]){
static char out[L+5];
__builtin_memcpy(out,name,sizeof out);
out[L-1]='.',out[L]='o',out[L+1]='u',out[L+2]='t',out[L+3]='\0';
freopen(out,"w",stdout);
}
#endif
public:
#ifndef LOCAL
IO():IN(stdin),OUT(stdout),p1(buf),p2(buf),p3(obuf){}
template<std::size_t L>
IO(const char(&name)[L]):IN(set_in(name)),OUT(set_out(name)),p1(buf),p2(buf),p3(obuf){}
template<std::size_t L>
IO(const char(&name)[L],bool in,bool out):IN(in?set_in(name):stdin),OUT(out?set_out(name):stdout),p1(buf),p2(buf),p3(obuf){}
~IO(){out_end();}
void out_end(){__builtin_fwrite(obuf,p3-obuf,1,OUT),p3=obuf;}
#else
IO(){}
template<std::size_t L>
IO(const char(&name)[L]){reset_stdin(name),reset_stdout(name);}
template<std::size_t L>
IO(const char(&name)[L],bool in,bool out){in&&(reset_stdin(name),0),out&&(reset_stdout(name),0);}
#endif
template<typename T>
void read(T&x){
x=0;bool flag=0;char ch=std_getchar();
for(;ch<'0'||ch>'9';ch=std_getchar()) if(ch=='-') flag=1;
if(flag) for(;ch>='0'&&ch<='9';ch=std_getchar()) x=(x<<1)+(x<<3)-(ch&15);
else for(;ch>='0'&&ch<='9';ch=std_getchar()) x=(x<<1)+(x<<3)+(ch&15);
}
template<typename T=int>
T read(){
T x=0;bool flag=0;char ch=std_getchar();
for(;ch<'0'||ch>'9';ch=std_getchar()) if(ch=='-') flag=1;
if(flag) for(;ch>='0'&&ch<='9';ch=std_getchar()) x=(x<<1)+(x<<3)-(ch&15);
else for(;ch>='0'&&ch<='9';ch=std_getchar()) x=(x<<1)+(x<<3)+(ch&15);
return x;
}
void read(char*str){
while((*str=std_getchar())==' '||*str=='\n');
while((*++str=std_getchar())!=' '&&*str!='\n');
*str=0;
}
void read(char&c){while((c=std_getchar()==' '||c=='\n'));}
template<typename T>
void write(T x){
static char sta[integral_length<T>];
int top=0;
if(is_unsigned_t<T>){
do sta[top++]=(x%10)|48,x/=10;
while(x);
}
else{
if(x<0){
std_putchar('-');
do sta[top++]=((-x)%10)|48,x/=10;
while(x);
}
else{
do sta[top++]=(x%10)|48,x/=10;
while(x);
}
}
while(top) std_putchar(sta[--top]);
}
void write(char x){std_putchar(x);}
void write(char*str){while(*str!='\0') std_putchar(*str++);}
void write(const char *str){while(*str!='\0') std_putchar(*str++);}
#ifdef LOCAL
template<typename T>
void error(T x){
static char sta[integral_length<T>];
int top=0;
if(is_unsigned_t<T>){
do sta[top++]=(x%10)|48,x/=10;
while(x);
}
else{
if(x<0){
err_putchar('-');
do sta[top++]=((-x)%10)|48,x/=10;
while(x);
}
else{
do sta[top++]=(x%10)|48,x/=10;
while(x);
}
}
while(top) err_putchar(sta[--top]);
}
void error(char x){err_putchar(x);}
void error(char*str){while(*str!='\0') err_putchar(*str++);}
void error(const char *str){while(*str!='\0') err_putchar(*str++);}
#endif
#ifdef _INITIALIZER_LIST
template<typename...Args>
void read(Args&...args){(void)LIST{(read(args),0)...};}
template<typename...Args>
void write(Args...args){(void)LIST{(write(args),0)...};}
template<typename...Args>
void writeln(Args...args){write(args...),std_putchar('\n');}
#ifdef LOCAL
template<typename...Args>
void error(Args...args){(void)LIST{(error(args),0)...};}
template<typename...Args>
void errorln(Args...args){error(args...),err_putchar('\n');}
#endif
#else
template<typename _Tp,typename...Args>
void read(_Tp&x,Args&...args){read(x),read(args...);}
void write(){}
template<typename _Tp,typename...Args>
void write(_Tp x,Args...args){write(x),write(args...);}
template<typename...Args>
void writeln(Args...args){write(args...),std_putchar('\n');}
#ifdef LOCAL
void error(){}
template<typename _Tp,typename...Args>
void error(_Tp x,Args...args){error(x),error(args...);}
template<typename...Args>
void errorln(Args...args){error(args...),err_putchar('\n');}
#endif
#endif
};
}
}
using namespace QL::IO;
IO lq;
constexpr int N=20;
using ull=unsigned long long;
ull f[N][N][2];
constexpr ull qw[N]{
1ull,
10ull,
100ull,
1000ull,
10000ull,
100000ull,
1000000ull,
10000000ull,
100000000ull,
1000000000ull,
10000000000ull,
100000000000ull,
1000000000000ull,
10000000000000ull,
100000000000000ull,
1000000000000000ull,
10000000000000000ull,
100000000000000000ull,
1000000000000000000ull,
10000000000000000000ull
},Inf=0x3f3f3f3f3f3f3f3f;
char n[N];
int len;
signed main(){
for(int Test_Cases=lq.read();Test_Cases--;){
static int cnt=0;
++cnt;
ull x;
int k;
lq.read(x,k);
static char sta[N]{};
static int top{};
top=0,len=1;
while(x%10==0) sta[++top]='0',x/=10;
while(x) n[len++]=(x%10)|48,x/=10;
for(int i=len;i<N;++i) n[i]='0';
__builtin_memset(f,0x3f,sizeof f);
f[0][0][0]=0;
for(int p=1;p<N;++p){
for(int j=0;j<=k;++j){
f[p][j][0]=f[p-1][j][0];
if(n[p]!='9') f[p][j][0]=std::min(f[p][j][0],f[p-1][j][1]);
if(j>=1){
int least='9'-n[p];
f[p][j][1]=least*qw[p-1]+f[p-1][j-1][1];
++least;
if(n[p]!='0') f[p][j][1]=std::min(f[p][j][1],least*qw[p-1]+f[p-1][j-1][0]);
}
}
}
ull ans=std::min(f[N-1][k][0],f[N-1][k][1]);
if(k) lq.write(ans);
else if(x){
int p=0;
for(int i=1;i<len&&!p;++i) if(n[i]!='9') p=i;
lq.write(p?qw[p-1]:qw[len-1]);
}
while(top) lq.write(sta[top--]);
// if(cnt!=69) while(top) lq.write(sta[top--]);
// else if(k==0) lq.write(' ',top,' ',x,"CZC");
lq.writeln();
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 0
Wrong Answer
time: 2ms
memory: 5620kb
input:
4 12345678 0 12345678 5 12345678 18 990099 5
output:
54322 999999999987654322 9910
result:
wrong answer 1st lines differ - expected: '1', found: ''