結果
問題 | No.5004 Room Assignment |
ユーザー |
![]() |
提出日時 | 2021-12-03 13:03:29 |
言語 | C++17(gcc12) (gcc 12.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 154 ms / 5,000 ms |
コード長 | 6,243 bytes |
コンパイル時間 | 1,820 ms |
実行使用メモリ | 22,392 KB |
スコア | 139,397,497 |
平均クエリ数 | 7612.63 |
最終ジャッジ日時 | 2021-12-03 13:03:51 |
合計ジャッジ時間 | 21,792 ms |
ジャッジサーバーID (参考情報) |
judge12 / judge11 |
純コード判定しない問題か言語 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 100 |
ソースコード
#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 = 100;int id = -1;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[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;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;}