#pragma GCC optimize("Ofast") #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; using ll = long long; using P = pair; template using V = vector; template using VV = V>; template bool chmin(T& t, const U& u) { if (t > u) { t = u; return 1; } else return 0; } template 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(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(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 parent; vector siz; map > 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 member; //V 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<<" "<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 players(MAX_p); V 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

operation; REP(i, N) { int s; cin >> s; players[num_p]= Player(num_p+1, s, tick); int value = 0; int id = -1; REP(r, SZ(rooms)) { if (rooms[r].nm > 3)continue; if (chmax(value, rooms[r].pre_value(&players[num_p], tick))) { id = r; } } 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(); //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; }