Submission #69285336

---

Source Code Expand

//#pragma GCC target ("avx")
//#pragma GCC optimize("O3")
//#pragma GCC optimize("unroll-loops")

#include <vector>
#include <iostream>
#include <random>
#include <algorithm>
#include <map>
#include <set>
#include <stack>
#include <queue>
#include <iomanip>
#include <functional> 
#include <sstream>

using namespace std;
using ll = long long int;

/*
how to compile
g++ main.cpp -o main -std=gnu++17 -Wall -Wextra -O2
time ./main < in.txt > out.txt
*/

clock_t start_time;
float limit_time = 1.8;

std::random_device rd;
std::mt19937 gen(rd());
 
//[low,high]
int random(int low, int high)
{
    std::uniform_int_distribution<> dist(low, high);
    return dist(gen);
}
double rand_double()
{
    std::uniform_real_distribution<double> dist(0.0, 1.0);
    return dist(gen);
}

struct comp2{
    bool operator()(const pair<ll,int> &p1,const pair<ll,int> &p2) const {
        if (p1.first == p2.first) {
            return p1.second < p2.second;
        } else {
            return p1.first < p2.first;
        }
    }
};



class MySolver{
    ll N,M,L,U;
    vector<ll> B;

    public:
    MySolver(){
        start_time = clock();
        cin >> N >> M >> L >> U;
    }

    void get_B(){
        B.resize(M);
        for(int i=0; i<M; i++) cin >> B[i];
    }

    ll solve1(){
        vector<ll> A(N, 1);
        int count = 0; 
        ll D = U-L;
        
        // for(int i=0; i<5; i++) A[count++] = L;
        for(int i=0; i<100; i++) A[count++] = L + i*(D/100);
        //D = D/65;
        D = D>>4;
        
        while(1){
            if(D==0) D=1;
            for(int i=0; i<20; i++){
                A[count++] = D + (D>>4)*i;
                if(count>=N) break;
            }
            if(count>=N) break;
            D = D>>1;
        }

        for(ll i : A) cout << i << " ";
        cout << endl;
        get_B();

        vector<pair<ll, int>> A2(N);
        for(int i=0; i<N; i++) A2[i] = {A[i], i};
        vector<vector<pair<ll, int>>> G(M+1);
        priority_queue<pair<ll, int>, vector<pair<ll, int>>, comp2> q;
        priority_queue<pair<ll, int>, vector<pair<ll, int>>, comp2> Z;

        for(int i=0; i<N; i++) q.push(A2[i]);
        for(int i=0; i<M; i++) Z.push(make_pair(B[i], i));


        while(q.size()!=0){
            pair<ll, int> now_q = q.top();
            pair<ll, int> now_z = Z.top();
            // cout << now_z.first << " " << now_q.first << endl;
            if(now_z.first >= now_q.first){
                q.pop(); Z.pop();
                G[now_z.second].push_back(now_q);
                now_z.first -= now_q.first;
                Z.push(now_z);
            }else{
                G[M].push_back(now_q);
                q.pop();
            }
        }

        vector<ll> BZ(M);
        for(int i=0; i<M; i++){
            pair<ll, int> now_z = Z.top(); Z.pop();
            BZ[now_z.second] = abs(now_z.first);
        }

        vector<int> ans(N, 0);
        for(int i=0; i<M; i++){
            for(auto now : G[i]){
                ans[now.second] = i+1;
            }
        }

        while(1){
            clock_t end_time = clock();
            const double time_ = static_cast<double> (end_time-start_time) / CLOCKS_PER_SEC * 1.0;
            if(time_ >= limit_time) break;

            int a1 = random(0, N-1);
            if(ans[a1]!=0) continue;
            int b1 = random(0, M-1);
            int ss = A[a1];
            
            for(auto i : G[b1]){
                if(i.first > A[a1]){
                    ss += i.first;
                }
            }
            vector<pair<ll, int>> tmp;
            
            if(abs(B[b1]-ss) < abs(BZ[b1])){
                tmp.push_back({A[a1], a1});
                // cout << BZ[b1] << " " << abs(B[b1]-ss) << endl;
                BZ[b1] = abs(B[b1]-ss);

                for(auto i : G[b1]){
                    if(i.first > A[a1]){
                        tmp.push_back(i);
                    }else{
                        ans[i.second] = 0;
                    }
                }
                G[b1] = tmp;
                ans[a1] = b1+1;
            }
            
        }

        for(int i=0; i<N; i++) cout << ans[i] << " ";
        cout << endl;

        ll score = 0.0;
        for(int i=0; i<M; i++){
            score += abs(BZ[i]);
        }
        return score;
    }

    ll solve(){
        ll score = solve1();

        return score;
    }

};




int main(){
    MySolver solver = MySolver();

    ll score = solver.solve();
    cerr << "score:" << (double)score << endl;

    return 0;
}

Submission Info

Judge Result