QOJ.ac
QOJ
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #680388 | #9249. Elimination Series Once More | confirm14478 | WA | 1ms | 8048kb | C++20 | 1.3kb | 2024-10-26 20:55:15 | 2024-10-26 20:55:17 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define int long long
int __ = 1;
using pii=pair<int,int>;
const int N=2e6+50;
int a[N],pos[N],ans[N];
int n,k,m;
bool check(int mid,int x)
{
int len=pow(2,x);
if(len>mid)return 0;
bool f=0;
for(int j=1;j<=m;j+=len)
{
int cnt=0;
for(int k=j;k<j+len;k++)
if(a[k]>mid)cnt++;
if(cnt<=k)f=1;
}
return f;
}
void solve(){
cin>>n>>k;
m=pow(2,n);
for(int i=1;i<=m;i++)
{
cin>>a[i];
pos[a[i]]=i;
}
if(k>=1)
{
int l=m+1,r;
int last=m;
for(int i=n;i>=0;i--)
{
if(last==0)break;
l=1,r=last;
while(l<r)
{
int mid=(l+r) >> 1;
if(check(mid,i)) r=mid;
else l=mid+1;
}
if(check(l,i)) {
for(int j=last;j>=l;j--)
ans[pos[j]]=i;
last=l-1;
}
}
}else
{
vector<int> b;
for(int i=1;i<=m;i++)b.push_back(a[i]);
for(int i=0;i<=n-1;i++)
{
vector<int>c;
for(int j=0;j<b.size();j+=2)
{
ans[pos[min(b[j],b[j+1])]]=i;
c.push_back(max(b[j],b[j+1]));
}
b=c;
}
ans[pos[b[0]]]=n;
}
for(int i=1;i<=m;i++)cout<<ans[i]<<" ";cout<<endl;
}
signed main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);cout.tie(nullptr);
// freopen("1.in.txt","r",stdin);
// cin >> __;
while (__--){
solve();
}
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 0ms
memory: 7824kb
input:
2 1 1 2 3 4
output:
0 1 1 2
result:
ok 4 number(s): "0 1 1 2"
Test #2:
score: 0
Accepted
time: 1ms
memory: 7980kb
input:
3 5 2 4 7 5 3 8 6 1
output:
1 2 2 2 1 3 2 0
result:
ok 8 numbers
Test #3:
score: 0
Accepted
time: 1ms
memory: 7964kb
input:
3 0 1 2 7 4 5 8 3 6
output:
0 1 2 0 0 3 0 1
result:
ok 8 numbers
Test #4:
score: 0
Accepted
time: 1ms
memory: 7912kb
input:
3 5 3 7 1 2 4 8 5 6
output:
1 2 0 1 2 3 2 2
result:
ok 8 numbers
Test #5:
score: 0
Accepted
time: 1ms
memory: 8044kb
input:
3 3 3 4 8 2 7 6 1 5
output:
1 2 3 1 2 2 0 2
result:
ok 8 numbers
Test #6:
score: 0
Accepted
time: 1ms
memory: 8048kb
input:
3 3 4 2 6 8 3 5 1 7
output:
2 1 2 3 1 2 0 2
result:
ok 8 numbers
Test #7:
score: 0
Accepted
time: 1ms
memory: 7896kb
input:
3 4 5 8 1 3 2 4 6 7
output:
2 3 0 1 1 2 2 2
result:
ok 8 numbers
Test #8:
score: -100
Wrong Answer
time: 0ms
memory: 7932kb
input:
3 1 7 3 8 6 5 2 4 1
output:
2 1 3 2 2 1 2 0
result:
wrong answer 4th numbers differ - expected: '1', found: '2'