QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #216167 | #5137. Tower | jason# | TL | 817ms | 3900kb | C++14 | 8.4kb | 2023-10-15 16:23:28 | 2023-10-15 16:23:28 |
Judging History
answer
#include<bits/stdc++.h>
#define pii pair<int,int>
#define x first
#define y second
#define int long long
#pragma GCC optimize(2)
#pragma GCC optimize(3,"Ofast","inline")
using namespace std;
namespace Fread{
const int SIZE=1<<16;
char buf[SIZE],*S,*T;
inline char getchar(){
if(S==T){
T=(S=buf)+fread(buf,1,SIZE,stdin);
if(S==T)return '\n';
}return *S++;
}
}
using namespace Fread;
namespace Fwrite{
const int SIZE=1<<16;
char buf[SIZE],*S=buf,*T=buf+SIZE;
inline void flush(){fwrite(buf,1,S-buf,stdout);S=buf;}
inline void putchar(char c){*S++ =c;if(S==T)flush();}
struct NTR {~NTR(){flush();}} ztr;
}
using namespace Fwrite;
#define getchar Fread::getchar
#define putchar Fwrite::putchar
namespace Fastio{
struct Reader{
template <typename T> Reader& operator >> (T &x){
x = 0;
short f = 1;
char c = getchar();
while(c<'0'||c>'9')
{if(c=='-')f*=-1;c=getchar();}
while(c>= '0'&&c<='9')
x=(x<<3)+(x<<1)+(c^48),c=getchar();
x *= f;
return *this;
}
Reader& operator>>(double &x){
x=0;
double t=0;
short f=1,s=0;
char c=getchar();
while((c<'0'||c>'9')&&c!='.')
{if(c=='-')f*=-1;c=getchar();}
while(c>='0'&&c<='9'&&c!='.')
x=x*10+(c^48),c=getchar();
if(c=='.')c=getchar();
else { x *= f; return *this; }
while(c>='0'&&c<='9')
t=t*10+(c^48),s++,c=getchar();
while (s--) t /= 10.0;
x = (x + t) * f;
return *this;
}
Reader& operator >> (long double &x){
x = 0;
long double t = 0;
short f = 1, s = 0;
char c = getchar();
while((c<'0'||c>'9')&&c!='.')
{if(c=='-')f*=-1;c=getchar();}
while (c >= '0' && c <= '9' && c != '.')
x = x * 10 + (c ^ 48), c = getchar();
if (c == '.') c = getchar();
else { x *= f; return *this; }
while (c >= '0' && c <= '9')
t = t * 10 + (c ^ 48), s++, c = getchar();
while (s--) t /= 10.0;
x = (x + t) * f;
return *this;
}
Reader& operator >> (__float128 &x){
x = 0;
__float128 t = 0;
short f = 1, s = 0;
char c = getchar();
while((c<'0'||c>'9')&&c!='.')
{if (c == '-')f*=-1;c=getchar();}
while (c >= '0' && c <= '9' && c != '.')
x = x * 10 + (c ^ 48), c = getchar();
if (c == '.') c = getchar();
else { x *= f; return *this; }
while (c >= '0' && c <= '9')
t = t * 10 + (c ^ 48), s++, c = getchar();
while (s--) t /= 10.0;
x = (x + t) * f;
return *this;
}
Reader& operator >> (char &c){
c = getchar();
while(c== ' '||c=='\n'||c=='\r')c=getchar();
return *this;
}
Reader& operator >> (char *str){
int len = 0;
char c = getchar();
while(c==' '||c=='\n'||c=='\r')c=getchar();
while (c!=' '&&c!='\n'&&c!='\r')
str[len++]=c,c=getchar();
str[len] = '0';
return *this;
}
Reader& operator >> (string &str){
str.clear();
char c = getchar();
while(c==' '||c=='\n'||c=='\r')c=getchar();
while(c!=' '&&c!='\n'&&c!='\r')
str.push_back(c),c = getchar();
return *this;
}
Reader() {}
} cin;
const char endl = '\n';
struct Writer{
const int Setprecision = 6;
typedef int mxdouble;
template <typename T> Writer& operator << (T x){
if (x == 0) { putchar('0'); return *this; }
if (x < 0) putchar('-'), x = -x;
static short sta[40];
short top = 0;
while (x > 0) sta[++top] = x % 10, x /= 10;
while (top>0)putchar(sta[top] + '0'),top--;
return *this;
}
Writer& operator << (double x){
if (x < 0) putchar('-'), x = -x;
mxdouble _ = x;
x -= (double)_;
static short sta[40];
short top = 0;
while(_>0)sta[++top]=_%10,_/=10;
if (top == 0) putchar('0');
while(top>0)putchar(sta[top]+'0'),top--;
putchar('.');
for(int i=0;i<Setprecision;i++)x*=10;
_ = x;
while(_>0)sta[++top]=_%10,_/=10;
for(int i=0;i<Setprecision-top;i++)putchar('0');
while (top > 0) putchar(sta[top] + '0'), top--;
return *this;
}
Writer& operator << (long double x){
if (x < 0) putchar('-'), x = -x;
mxdouble _ = x;
x -= (long double)_;
static short sta[40];
short top = 0;
while (_ > 0) sta[++top] = _ % 10, _ /= 10;
if (top == 0) putchar('0');
while (top > 0) putchar(sta[top] + '0'), top--;
putchar('.');
for (int i = 0; i < Setprecision; i++) x *= 10;
_ = x;
while (_ > 0) sta[++top] = _ % 10, _ /= 10;
for(int i=0;i<Setprecision-top;i++)putchar('0');
while (top > 0) putchar(sta[top] + '0'), top--;
return *this;
}
Writer& operator << (__float128 x){
if (x < 0) putchar('-'), x = -x;
mxdouble _ = x;
x -= (__float128)_;
static short sta[40];
short top = 0;
while (_ > 0) sta[++top] = _ % 10, _ /= 10;
if (top == 0) putchar('0');
while (top > 0) putchar(sta[top] + '0'), top--;
putchar('.');
for (int i = 0; i < Setprecision; i++) x *= 10;
_ = x;
while (_ > 0) sta[++top] = _ % 10, _ /= 10;
for(int i=0;i<Setprecision-top;i++)putchar('0');
while (top > 0) putchar(sta[top] + '0'), top--;
return *this;
}
Writer& operator <<(char c)
{putchar(c);return *this;}
Writer& operator << (char *str){
int cur = 0;
while (str[cur]) putchar(str[cur++]);
return *this;
}
Writer& operator << (const char *str){
int cur = 0;
while (str[cur]) putchar(str[cur++]);
return *this;
}
Writer& operator << (string str){
int st = 0, ed = str.size();
while (st < ed) putchar(str[st++]);
return *this;
}
Writer() {}
} cout;
}
using namespace Fastio;
#define cin Fastio::cin
#define cout Fastio::cout
#define endl Fastio::endl
const int N=2e5+5;
int a[N];
void slove(){
int n,m;
cin>>n>>m;
unordered_set<int> st;
vector<int> v[n+1];
for(int i=1,tmp;i<=n;++i){
cin>>a[i];
tmp=a[i];
while(tmp){
st.insert(tmp);
v[i].push_back(tmp);
tmp/=2;
}
reverse(v[i].begin(),v[i].end());
}
int ans=1e9;
for(auto &h:st){
// cout<<"h : "<<h<<endl;
for(int i=30;i>=-30;--i){
if(h+i<=0) break;
int now=h+i;
// cout<<"now : "<<now<<endl;
vector<int> tmp;
for(int i=1;i<=n;++i){
int id=lower_bound(v[i].begin(),v[i].end(),now)-v[i].begin();
int x,y;
if(id==v[i].size()){
x=1e9;
y=now-v[i][id-1];
}
else{
x=v[i][id]-now + v[i].size()-id-1;
y=now-v[i][id]/2 + v[i].size()-id;
}
// cout<<"x y : "<<x<<" "<<y<<endl;
tmp.push_back(min(x,y));
}
sort(tmp.begin(),tmp.end());
int res=0;
for(int i=0;i<n-m;++i){
res += tmp[i];
}
ans = min(ans,res);
}
}
cout<<ans<<"\n";
}
signed main()
{
ios::sync_with_stdio(0);
int t;cin>>t;
while(t--){
slove();
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 3828kb
input:
3 2 0 2 6 5 0 1 2 3 4 5 5 3 1 2 3 4 5
output:
2 4 1
result:
ok 3 number(s): "2 4 1"
Test #2:
score: 0
Accepted
time: 310ms
memory: 3688kb
input:
10 272 118 11 14 49 94 71 62 46 45 74 22 15 36 7 37 27 35 96 85 75 78 76 64 23 59 17 35 71 28 96 82 5 66 2 48 57 31 88 10 61 73 79 23 19 52 39 76 48 98 5 39 48 51 90 90 60 27 47 24 24 56 48 27 39 21 38 18 20 9 62 83 47 15 51 22 73 74 7 80 64 60 86 74 59 7 84 38 99 31 42 60 52 41 63 88 59 90 77 40 68...
output:
454 3 436 108 570 636 994 227 656 50
result:
ok 10 numbers
Test #3:
score: 0
Accepted
time: 242ms
memory: 3692kb
input:
10 133 89 20 70 6 45 4 72 38 7 18 1 82 39 69 85 5 36 1 62 30 47 68 55 7 41 7 42 7 61 11 82 2 80 80 93 29 30 42 58 73 26 99 67 60 94 61 46 47 54 44 50 35 88 61 17 23 97 90 28 16 47 75 35 28 14 42 63 26 40 95 58 26 25 26 83 93 56 17 27 7 90 91 28 53 49 47 84 55 52 11 34 14 74 40 65 84 32 99 46 1 21 31...
output:
88 1361 128 246 29 83 3 677 96 382
result:
ok 10 numbers
Test #4:
score: 0
Accepted
time: 817ms
memory: 3900kb
input:
10 500 50 67 93 11 58 54 40 37 3 92 96 91 20 46 5 21 43 3 2 7 47 27 81 14 53 86 21 46 51 86 22 42 14 52 38 42 25 34 29 84 42 43 96 11 100 27 60 48 15 13 69 58 16 14 58 17 94 8 71 39 38 25 37 100 58 99 56 65 84 94 63 25 34 13 73 83 83 69 60 70 15 15 90 7 11 88 69 13 26 99 28 16 97 32 40 76 62 41 5 9 ...
output:
1608 169 144 983 1087 1317 882 75 32 1259
result:
ok 10 numbers
Test #5:
score: -100
Time Limit Exceeded
input:
10 500 414 503 505 103 380 946 153 952 386 890 306 522 147 499 784 643 121 264 344 549 72 299 314 45 688 97 747 442 528 752 830 335 78 159 218 748 331 259 375 479 883 202 402 595 738 430 184 874 762 864 743 733 209 821 616 868 543 314 161 100 638 439 943 732 962 243 776 803 423 749 367 731 594 993 9...