結果

問題 No.5004 Room Assignment
ユーザー highjumphighjump
提出日時 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
権限があれば一括ダウンロードができます

ソースコード

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);
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;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0