#721416 (C++17) No.5004 Room Assignment

• 問題: No.5004 Room Assignment
• ユーザー: highjump
• 提出日時: 2021-12-03 00:41:10
• 言語: C++17 (gcc 12.3.0 + boost 1.83.0)
• 結果: AC
• 実行時間: 164 ms / 5,000 ms
• コード長: 5,898 bytes
• コンパイル時間: 1,696 ms
• 実行使用メモリ: 22,392 KB
• スコア: 138,046,308
• 平均クエリ数: 7560.98
• 最終ジャッジ日時: 2021-12-03 00:41:32
• 合計ジャッジ時間: 21,263 ms
• ジャッジサーバーID （参考情報）: judge13 / judge11

入力	結果	実行時間; 実行使用メモリ
testcase_00	AC	136 ms; 22,224 KB
testcase_01	AC	135 ms; 21,924 KB
testcase_02	AC	135 ms; 21,960 KB
testcase_03	AC	155 ms; 22,032 KB
testcase_04	AC	137 ms; 21,924 KB
testcase_05	AC	136 ms; 21,960 KB
testcase_06	AC	134 ms; 21,924 KB
testcase_07	AC	137 ms; 21,948 KB
testcase_08	AC	136 ms; 21,912 KB
testcase_09	AC	135 ms; 21,960 KB
testcase_10	AC	135 ms; 21,972 KB
testcase_11	AC	136 ms; 21,768 KB
testcase_12	AC	154 ms; 21,960 KB
testcase_13	AC	135 ms; 21,792 KB
testcase_14	AC	135 ms; 21,948 KB
testcase_15	AC	134 ms; 22,092 KB
testcase_16	AC	134 ms; 21,948 KB
testcase_17	AC	136 ms; 21,924 KB
testcase_18	AC	137 ms; 21,924 KB
testcase_19	AC	133 ms; 21,972 KB
testcase_20	AC	134 ms; 21,900 KB
testcase_21	AC	144 ms; 22,032 KB
testcase_22	AC	135 ms; 21,924 KB
testcase_23	AC	136 ms; 21,780 KB
testcase_24	AC	135 ms; 21,936 KB
testcase_25	AC	136 ms; 21,960 KB
testcase_26	AC	136 ms; 21,768 KB
testcase_27	AC	135 ms; 21,960 KB
testcase_28	AC	135 ms; 21,960 KB
testcase_29	AC	138 ms; 22,140 KB
testcase_30	AC	147 ms; 21,816 KB
testcase_31	AC	131 ms; 21,924 KB
testcase_32	AC	136 ms; 21,936 KB
testcase_33	AC	138 ms; 21,924 KB
testcase_34	AC	133 ms; 22,104 KB
testcase_35	AC	134 ms; 22,092 KB
testcase_36	AC	135 ms; 21,836 KB
testcase_37	AC	134 ms; 21,948 KB
testcase_38	AC	139 ms; 21,972 KB
testcase_39	AC	142 ms; 21,948 KB
testcase_40	AC	138 ms; 21,948 KB
testcase_41	AC	136 ms; 21,960 KB
testcase_42	AC	137 ms; 22,152 KB
testcase_43	AC	138 ms; 22,104 KB
testcase_44	AC	138 ms; 21,816 KB
testcase_45	AC	135 ms; 21,900 KB
testcase_46	AC	136 ms; 21,768 KB
testcase_47	AC	146 ms; 22,080 KB
testcase_48	AC	138 ms; 21,948 KB
testcase_49	AC	136 ms; 21,936 KB
testcase_50	AC	136 ms; 22,392 KB
testcase_51	AC	138 ms; 21,936 KB
testcase_52	AC	133 ms; 21,944 KB
testcase_53	AC	135 ms; 21,840 KB
testcase_54	AC	135 ms; 21,900 KB
testcase_55	AC	136 ms; 22,056 KB
testcase_56	AC	153 ms; 21,804 KB
testcase_57	AC	136 ms; 22,092 KB
testcase_58	AC	135 ms; 22,128 KB
testcase_59	AC	138 ms; 22,092 KB
testcase_60	AC	137 ms; 21,840 KB
testcase_61	AC	136 ms; 21,972 KB
testcase_62	AC	137 ms; 22,152 KB
testcase_63	AC	136 ms; 22,164 KB
testcase_64	AC	138 ms; 21,948 KB
testcase_65	AC	154 ms; 21,968 KB
testcase_66	AC	136 ms; 22,092 KB
testcase_67	AC	136 ms; 22,224 KB
testcase_68	AC	137 ms; 21,924 KB
testcase_69	AC	139 ms; 22,140 KB
testcase_70	AC	134 ms; 21,888 KB
testcase_71	AC	134 ms; 21,948 KB
testcase_72	AC	137 ms; 22,152 KB
testcase_73	AC	139 ms; 21,960 KB
testcase_74	AC	164 ms; 21,924 KB
testcase_75	AC	151 ms; 21,780 KB
testcase_76	AC	135 ms; 21,948 KB
testcase_77	AC	135 ms; 21,972 KB
testcase_78	AC	135 ms; 21,960 KB
testcase_79	AC	134 ms; 22,212 KB
testcase_80	AC	136 ms; 21,924 KB
testcase_81	AC	134 ms; 22,020 KB
testcase_82	AC	140 ms; 22,128 KB
testcase_83	AC	150 ms; 21,936 KB
testcase_84	AC	136 ms; 21,984 KB
testcase_85	AC	137 ms; 21,888 KB
testcase_86	AC	137 ms; 21,912 KB
testcase_87	AC	135 ms; 21,888 KB
testcase_88	AC	135 ms; 21,780 KB
testcase_89	AC	137 ms; 21,972 KB
testcase_90	AC	136 ms; 21,780 KB
testcase_91	AC	148 ms; 21,936 KB
testcase_92	AC	146 ms; 22,020 KB
testcase_93	AC	134 ms; 21,972 KB
testcase_94	AC	139 ms; 21,912 KB
testcase_95	AC	136 ms; 21,936 KB
testcase_96	AC	135 ms; 22,128 KB
testcase_97	AC	136 ms; 21,948 KB
testcase_98	AC	136 ms; 21,780 KB
testcase_99	AC	139 ms; 21,936 KB

ソースコード

#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);

    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);
            int value = 150;
            int id = -1;
            REP(r, SZ(rooms)) {
                if (rooms[r].nm > 3)continue;
                if (max(rooms[r].ma, s) - min(rooms[r].mi, s) > 3)continue;
                if (chmax(value, rooms[r].pre_value(&players[num_p], tick))) {
                    id = r;
                }
            }
            //cerr << value << endl;
            if (id == -1) {
                Room room(&players[num_p],tick);
                rooms.push_back(room);
            }
            else {
                operation.emplace_back(rooms[id].id, num_p+1);
                rooms[id].add(&players[num_p], tick);
            }
            num_p++;

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

    }


    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;
}