QOJ.ac

QOJ

ID	题目	提交者	结果	用时	内存	语言	文件大小	提交时间	测评时间
#630812	#5137. Tower	7islands^#	WA	110ms	3584kb	C++17	3.0kb	2024-10-11 20:31:13	2024-10-11 20:31:14

Judging History

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

[2024-10-11 20:31:14]
评测

测评结果：WA
用时：110ms
内存：3584kb

查看

[2024-10-11 20:31:13]
提交

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(a[ee[i].pos]>mid) up--;
                else if(a[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(a[ee[i].pos]>mid) up--;
                else if(a[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;
}

源文件, 语言: C++17

详细

Test #1:

score: 100

Accepted

time: 0ms

memory: 3560kb

input:

output:

2
4
1

result:

ok 3 number(s): "2 4 1"

Test #2:

score: -100

Wrong Answer

time: 110ms

memory: 3584kb

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:

result:

wrong answer 3rd numbers differ - expected: '436', found: '437'