結果

問題 No.5004 Room Assignment
ユーザー highjumphighjump
提出日時 2021-12-11 00:47:37
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 163 ms / 5,000 ms
コード長 9,220 bytes
コンパイル時間 2,264 ms
実行使用メモリ 22,392 KB
スコア 140,046,304
平均クエリ数 7615.83
最終ジャッジ日時 2021-12-11 00:48:03
合計ジャッジ時間 23,845 ms
ジャッジサーバーID
（参考情報） 		judge12 / judge13
純コード判定しない問題か言語
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 147 ms
21,924 KB
testcase_01 AC 149 ms
22,020 KB
testcase_02 AC 150 ms
21,908 KB
testcase_03 AC 148 ms
22,152 KB
testcase_04 AC 149 ms
21,960 KB
testcase_05 AC 147 ms
22,152 KB
testcase_06 AC 146 ms
21,792 KB
testcase_07 AC 149 ms
22,020 KB
testcase_08 AC 152 ms
21,960 KB
testcase_09 AC 148 ms
21,924 KB
testcase_10 AC 149 ms
22,200 KB
testcase_11 AC 150 ms
22,356 KB
testcase_12 AC 150 ms
22,008 KB
testcase_13 AC 152 ms
22,020 KB
testcase_14 AC 150 ms
21,780 KB
testcase_15 AC 146 ms
21,900 KB
testcase_16 AC 146 ms
22,020 KB
testcase_17 AC 153 ms
22,392 KB
testcase_18 AC 150 ms
21,792 KB
testcase_19 AC 148 ms
22,392 KB
testcase_20 AC 152 ms
21,780 KB
testcase_21 AC 151 ms
22,092 KB
testcase_22 AC 147 ms
21,936 KB
testcase_23 AC 148 ms
21,936 KB
testcase_24 AC 149 ms
21,900 KB
testcase_25 AC 151 ms
21,780 KB
testcase_26 AC 149 ms
21,732 KB
testcase_27 AC 149 ms
21,780 KB
testcase_28 AC 148 ms
22,092 KB
testcase_29 AC 151 ms
21,708 KB
testcase_30 AC 148 ms
22,056 KB
testcase_31 AC 147 ms
21,972 KB
testcase_32 AC 150 ms
22,152 KB
testcase_33 AC 151 ms
21,948 KB
testcase_34 AC 148 ms
21,900 KB
testcase_35 AC 147 ms
22,368 KB
testcase_36 AC 148 ms
22,032 KB
testcase_37 AC 152 ms
21,972 KB
testcase_38 AC 156 ms
21,900 KB
testcase_39 AC 150 ms
21,924 KB
testcase_40 AC 149 ms
21,900 KB
testcase_41 AC 147 ms
21,972 KB
testcase_42 AC 150 ms
21,936 KB
testcase_43 AC 153 ms
21,888 KB
testcase_44 AC 149 ms
21,780 KB
testcase_45 AC 150 ms
21,936 KB
testcase_46 AC 160 ms
21,924 KB
testcase_47 AC 150 ms
21,804 KB
testcase_48 AC 153 ms
22,224 KB
testcase_49 AC 150 ms
21,936 KB
testcase_50 AC 148 ms
21,900 KB
testcase_51 AC 150 ms
21,912 KB
testcase_52 AC 147 ms
21,780 KB
testcase_53 AC 152 ms
22,152 KB
testcase_54 AC 157 ms
21,912 KB
testcase_55 AC 148 ms
22,356 KB
testcase_56 AC 148 ms
22,092 KB
testcase_57 AC 149 ms
21,792 KB
testcase_58 AC 148 ms
21,888 KB
testcase_59 AC 150 ms
21,948 KB
testcase_60 AC 147 ms
21,936 KB
testcase_61 AC 149 ms
21,912 KB
testcase_62 AC 154 ms
22,128 KB
testcase_63 AC 163 ms
21,936 KB
testcase_64 AC 146 ms
21,924 KB
testcase_65 AC 147 ms
21,936 KB
testcase_66 AC 148 ms
21,900 KB
testcase_67 AC 147 ms
21,828 KB
testcase_68 AC 148 ms
21,948 KB
testcase_69 AC 150 ms
22,128 KB
testcase_70 AC 154 ms
21,780 KB
testcase_71 AC 149 ms
22,140 KB
testcase_72 AC 149 ms
21,936 KB
testcase_73 AC 146 ms
21,792 KB
testcase_74 AC 149 ms
21,960 KB
testcase_75 AC 149 ms
22,356 KB
testcase_76 AC 148 ms
22,080 KB
testcase_77 AC 148 ms
21,888 KB
testcase_78 AC 159 ms
21,924 KB
testcase_79 AC 152 ms
21,972 KB
testcase_80 AC 152 ms
21,888 KB
testcase_81 AC 146 ms
21,948 KB
testcase_82 AC 147 ms
21,984 KB
testcase_83 AC 147 ms
21,900 KB
testcase_84 AC 149 ms
22,116 KB
testcase_85 AC 152 ms
21,924 KB
testcase_86 AC 151 ms
21,780 KB
testcase_87 AC 161 ms
22,152 KB
testcase_88 AC 147 ms
22,020 KB
testcase_89 AC 146 ms
21,936 KB
testcase_90 AC 150 ms
21,780 KB
testcase_91 AC 148 ms
21,948 KB
testcase_92 AC 146 ms
21,768 KB
testcase_93 AC 148 ms
22,152 KB
testcase_94 AC 149 ms
22,356 KB
testcase_95 AC 152 ms
21,960 KB
testcase_96 AC 149 ms
21,924 KB
testcase_97 AC 151 ms
21,948 KB
testcase_98 AC 150 ms
21,960 KB
testcase_99 AC 150 ms
22,152 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#pragma GCC optimize("Ofast")
#include <iostream>
#include <algorithm>
#include <string>
#include <cstdlib>
#include <cmath>
#include <iomanip>
#include <cctype>
#include <sstream>
#include <vector>
#include <stack>
#include <deque>
#include <queue>
#include <list>
#include <set>
#include <map>
#include <unordered_map>  
#include <chrono>
#include <random>

using namespace std;

using ll = long long;
using P = pair<int, int>;
template <class T>using V = vector<T>;
template <class T>using VV = V<V<T>>;
template <class T, class U>bool chmin(T& t, const U& u) { if (t > u) { t = u; return 1; } else return 0; }
template <class T, class U>bool chmax(T& t, const U& u) { if (t < u) { t = u; return 1; } else return 0; }

#define REP(i,n) for(int i=0;i<int(n);i++)
#define FOR(i,a,b) for(int i=int(a);i<=int(b);i++)
#define FORD(i,a,b) for(int i=int(a);i>=int(b);i--)
#define MP make_pair
#define SZ(x) int(x.size())
#define ALL(x) x.begin(),x.end()
#define INF 10001000
#define endl "\n"

chrono::system_clock::time_point t_start;
const double TIME_LIMIT1 = 500, TIME_LIMIT = 2930;
double last_update = 0, t_diff;
double start_temp, end_temp;

mt19937 rng;
using uni_int = uniform_int_distribution<>;
using uni_real = uniform_real_distribution<>;
//uni_real dist(0.0, 1.0);
//uni_int dist_int(0, 7);

/*
double prob = exp((next_score-current_score) / get_temp());
if (prob > dist(rng)) {
*/

void get_time() {
    auto t_now = chrono::system_clock::now();
    t_diff = chrono::duration_cast<chrono::milliseconds>(t_now - t_start).count();
}

double get_temp() {
    start_temp = 10000; end_temp = 0.1;
    return start_temp + (end_temp - start_temp) * ((t_diff - TIME_LIMIT1) / (TIME_LIMIT - TIME_LIMIT1));
}

class UnionFind {
public:
    vector<ll> parent;
    vector<ll> siz;
    map<ll, vector<ll> > group;
    ll n;

    UnionFind(ll n_) :n(n_), parent(n_), siz(n_, 1) {
        for (ll i = 0; i < n; i++) { parent[i] = i; }
    }

    ll root(ll x) {
        if (parent[x] == x) return x;
        return parent[x] = root(parent[x]);
    }

    bool unite(ll x, ll y) {
        ll rx = root(x);
        ll ry = root(y);
        if (rx == ry) return false;
        if (siz[rx] < siz[ry]) swap(rx, ry);
        siz[rx] += siz[ry];
        parent[ry] = rx;
        return true;
    }

    bool same(ll x, ll y) {
        return root(x) == root(y);
    }

    ll size(ll x) {
        return siz[root(x)];
    }
};

class Player {
public:
    int id = 0;
    int skill = 0;
    int time = 0;
    int room = -1;

    Player() {};
    Player(int i,int s, int t) :id(i),skill(s), time(t) {};

    void set_room(int r) {
        room = r;
    }
};

class Room {
public:
    int id = -1;
    int ma = -1;
    int mi = INF;
    int su = 0;
    int pe = 0;
    int nm = 0;
    V<int> member;

    //V<Player*> member;

    Room() {};
    Room(Player* p,int t) {
        id = p->id;
        chmin(mi, p->skill);
        chmax(ma, p->skill);
        su = p->time;
        pe = 0;
        nm = 1;
        //this->show();
        member.push_back(id);
    }

    void add(Player* p, int t) {
        //chmin(id, p->id);
        chmin(mi, p->skill);
        chmax(ma, p->skill);
        pe += nm * (t - p->time);
        //cerr << t<<" "<<nm * t << " " << su << endl;
        pe += nm * t - su;
        su += p->time;
        nm++;
        member.push_back(p->id);
        //this->show();
    }

    int pre_value(Player* p, int t) {
        int res = 0;
        int c = nm*(nm+1)/2;
        res += c * (200 - (max(ma, p->skill) - min(mi, p->skill)) 
            * (max(ma, p->skill) - min(mi, p->skill)));
        res -= pe;
        res -= nm * (t - p->time);
        res -= nm * t - su;
        return max(res,0);
    }

    int get_value() {
        int res = 0;
        int c = nm * (nm - 1) / 2;
        res += c * (200 - (ma - mi) * (ma - mi));
        res -= pe;
        return max(res, 0);
    }

    void show() {
        cerr << id << " " << ma << " " << mi << " " << su <<" "<< pe<<" " << nm << endl;
    }
};

int T, R, N;
int MAX_p = 5400,num_p=0;
V<Player> players(MAX_p);
V<Room> rooms;

signed main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    cout << fixed << setprecision(15);
    cerr << fixed << setprecision(15);
    t_start = chrono::system_clock::now();

    cin >> T >> R;
    //UnionFind rooms(MAX_p);
    UnionFind u(N);
    V<int> pool;
    REP(tick, T) {
        cin >> N;
        //cerr << tick << " " << N << endl;
        V<P> operation;

        REP(i, N) {
            int s; cin >> s;
            players[num_p]= Player(num_p+1, s, tick);
            pool.push_back(num_p);
            num_p++;
        }

        for (auto itr = pool.begin(); itr != pool.end(); itr++) {
            int p = *itr;
            int value = 100;
            int id = -1;
            int s = players[p].skill;
            REP(r, SZ(rooms)) {
                if (rooms[r].nm > 3)continue;
                if (tick - players[rooms[r].id].time > 150)continue;
                if (s > rooms[r].ma || s < rooms[r].mi)continue;
                if (chmax(value, rooms[r].pre_value(&players[p], tick))) {
                    id = r;
                }
            }
            if (id != -1) {
                operation.emplace_back(rooms[id].id, p + 1);
                rooms[id].add(&players[p], tick);
                itr = pool.erase(itr);
                itr--;
            }
        }

        for (auto itr = pool.begin(); itr != pool.end(); itr++) {
            int p = *itr;
            int value = 100;
            int id = -1;
            int s = players[p].skill;
            REP(r, SZ(rooms)) {
                if (rooms[r].nm > 3)continue;
                if (tick - players[rooms[r].id].time > 150)continue;
                if (max(rooms[r].ma, s) - min(rooms[r].mi, s) > 2)continue;
                if (chmax(value, rooms[r].pre_value(&players[p], tick))) {
                    id = r;
                }
            }
            if (id != -1) {
                operation.emplace_back(rooms[id].id, p + 1);
                rooms[id].add(&players[p], tick);
                itr = pool.erase(itr);
                itr--;
            }
        }

        for (auto itr = pool.begin(); itr != pool.end(); itr++) {
            int p = *itr;
            int value = 100;
            int id = -1;
            int s = players[p].skill;
            REP(r, SZ(rooms)) {
                if (rooms[r].nm > 3)continue;
                if (tick - players[rooms[r].id].time > 150)continue;
                if (abs(s - 50) <= 25 && max(rooms[r].ma, s) - min(rooms[r].mi, s) > 3)continue;
                if (abs(s - 50) > 25 && max(rooms[r].ma, s) - min(rooms[r].mi, s) > 4)continue;
                if (chmax(value, rooms[r].pre_value(&players[p], tick))) {
                    id = r;
                }
            }
            //cerr << value << endl;
            if (id == -1) {
                if (tick > 3500)continue;
                Room room(&players[p], tick);
                rooms.push_back(room);
            }
            else {
                operation.emplace_back(rooms[id].id, p + 1);
                rooms[id].add(&players[p], tick);
            }
            itr = pool.erase(itr);
            itr--;
        }

        if (SZ(pool) > 0) {
            for (auto itr = pool.begin(); itr != pool.end(); itr++) {
                int p = *itr;
                int value = 50;
                int id = -1;
                int s = players[p].skill;
                REP(r, SZ(rooms)) {
                    if (rooms[r].nm > 3)continue;
                    if (tick - players[rooms[r].id].time > 150)continue;
                    if (abs(s - 50) <= 25 && max(rooms[r].ma, s) - min(rooms[r].mi, s) > 3)continue;
                    if (abs(s - 50) > 25 && max(rooms[r].ma, s) - min(rooms[r].mi, s) > 4)continue;
                    if (chmax(value, rooms[r].pre_value(&players[p], tick))) {
                        id = r;
                    }
                }
                //cerr << value << endl;
                if (id == -1) {
                    Room room(&players[p], tick);
                    rooms.push_back(room);
                }
                else {
                    operation.emplace_back(rooms[id].id, p + 1);
                    rooms[id].add(&players[p], tick);
                }
                itr = pool.erase(itr);
                itr--;
            }

        }


        cout << SZ(operation) << endl;
        for (P p : operation)cout << p.first << " " << p.second << endl;
        cout.flush();
    }
    int score = 0;
    V<int> cnt(5);
    for (auto r : rooms) {
        score += r.get_value();
        //if(r.nm>1)cerr << r.ma<<" "<<r.mi <<" "<<r.id<<" "<<r.member[r.nm-1]<< endl;
        cnt[r.nm]++;
        //for (int s : r.member)cerr << players[s].time << " ";
        //cerr << endl;
        //r.show();

    }
    //cerr << cnt[1] << " " << cnt[2] << " " << cnt[3] << " " << cnt[4] << endl;

    get_time();

    cerr << "time:  " << int(t_diff) << " ms" << endl;
    cerr << "score: " << score << endl;
    //cerr << "last:  " << last_update << endl;
    //cerr << "cnt:   " << cnt << endl;
    //cerr << "update:" << update_cnt << endl;
    return 0;
}
0