QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#630795#5137. Tower7islands#WA 143ms3596kbC++173.0kb2024-10-11 20:27:122024-10-11 20:27:12

Judging History

你现在查看的是最新测评结果

  • [2024-10-11 20:27:12]
  • 评测
  • 测评结果:WA
  • 用时:143ms
  • 内存:3596kb
  • [2024-10-11 20:27:12]
  • 提交

answer

#include <bits/stdc++.h>
#define int long long
#define endl '\n'
#define pii pair<int,int>
using namespace std;
int a[510],ans[510];
int e[510];
int n,m;
struct node{
    int pos,val;
    bool operator < (const node a)const{
        return val<a.val;
    }
}ee[510];
void solve(){
    cin>>n>>m;
    priority_queue<pii> q;
    for(int i = 1;i<=n;i++){
        cin>>a[i];
        ans[i] = 0;
        q.push(make_pair(a[i],i));
    }
    int cnt = 0;
    int res = 1e17;
    
    int l = 1,r = q.top().first;
        while(l<=r){
            int mid = l+r>>1;
            int down=0,up = 0,on = 0;
            int t = 0;
            for(int i = 1;i<=n;i++){
                if(a[i] < mid) down ++;
                else if(a[i] > mid) up++;
                else on++;
                ee[i].val = abs(a[i]-mid) + ans[i];
                ee[i].pos = i;
                t+=abs(a[i]-mid) + ans[i];
            }
            sort(ee+1,ee+1+n);
            for(int i = n;i>0&&i>n-m;i--){
                t -=ee[i].val;
                if(ee[i].pos>mid) up--;
                else if(ee[i].pos<mid) down--;
                else on--;
            }
            if(t<res) res = t;
            if(up<down){
                if(up+on<down){
                    r=mid-1;
                }
                else break;
            }
            else if(down<up){
                if(down+on<up){
                    l = mid+1;
                }
                else break;
            }
            else break;
        }
    
    while(!q.empty()){
        int pos = q.top().second;
        int val = q.top().first;
        q.pop();
        if(val == 1) break;
        val /= 2;
        a[pos] = val;
        cnt ++;
        q.push(make_pair(val,pos));
        ans[pos] ++ ;
        int l = 1,r = q.top().first;
        while(l<=r){
            int mid = l+r>>1;
            int down=0,up = 0,on = 0;
            int t = 0;
            for(int i = 1;i<=n;i++){
                if(a[i] < mid) down ++;
                else if(a[i] > mid) up++;
                else on++;
                ee[i].val = abs(a[i]-mid) + ans[i];
                ee[i].pos = i;
                t+=abs(a[i]-mid) + ans[i];
            }
            sort(ee+1,ee+1+n);
            for(int i = n;i>0&&i>n-m;i--){
                t -=ee[i].val;
                if(ee[i].pos>mid) up--;
                else if(ee[i].pos<mid) down--;
                else on--;
            }
            if(t<res) res = t;
            if(up<down){
                if(up+on<down){
                    r=mid-1;
                }
                else break;
            }
            else if(down<up){
                if(down+on<up){
                    l = mid+1;
                }
                else break;
            }
            else break;
        }
    }
    cout<<res<<endl;

}
signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    int t=1;
    cin>>t;
    while(t--){
        solve();
    }
    return 0;
}

详细

Test #1:

score: 100
Accepted
time: 0ms
memory: 3572kb

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: -100
Wrong Answer
time: 143ms
memory: 3596kb

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
228
656
51

result:

wrong answer 8th numbers differ - expected: '227', found: '228'