| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 378271 |
2021-03-16T11:12:22 Z |
pit4h |
Meetings (JOI19_meetings) |
C++14 |
|
1006 ms |
262148 KB |
#include "meetings.h"
#include<bits/stdc++.h>
using namespace std;
int n;
int RAND(int l, int r, mt19937 rng) {
return uniform_int_distribution<int>(l, r)(rng);
}
void solve(vector<int> v, mt19937 rng) {
if((int)v.size()<=1) return;
if((int)v.size()==2) {
//cerr<<"bridge: "<<v[0]<<' '<<v[1]<<'\n';
Bridge(min(v[0], v[1]), max(v[0], v[1]));
return;
}
int sz = v.size();
int v1 = RAND(0, sz-1, rng), v2 = RAND(0, sz-2, rng);
if(v2>=v1) v2++;
//cerr<<"solve [";
/*for(int i=0; i<sz; ++i) {
cerr<<v[i];
if(i<sz-1) cerr<<' ';
else cerr<<"] ";
}
cerr<<v[v1]<<' '<<v[v2]<<" "<<n<<'\n';
*/
vector<vector<int>> vec(n);
vec[v[v1]].push_back(v[v1]);
vec[v[v2]].push_back(v[v2]);
vector<int> path = {v[v1], v[v2]};
for(int i=0; i<sz; ++i) {
if(i == v1 || i==v2) continue;
int u = Query(v[v1], v[v2], v[i]);
//cerr<<v[i]<<": "<<u<<'\n';
if(u == v[i]) {
path.push_back(v[i]);
}
vec[u].push_back(v[i]);
}
if((int)path.size() == 3) {
//cerr<<"Bridge: "<<v[0]<<' '<<path[2]<<'\n';
//cerr<<"Bridge: "<<v[1]<<' '<<path[2]<<'\n';
Bridge(min(v[v1], path[2]), max(v[v1], path[2]));
Bridge(min(v[v2], path[2]), max(v[v2], path[2]));
}
else {
solve(path, rng);
}
for(int i=0; i<n; ++i) {
//cerr<<' '<<i<<" - "<<vec[i].size()<<'\n';
solve(vec[i], rng);
}
}
void Solve(int N) {
n = N;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
vector<int> v;
for(int i=0; i<N; ++i) {
v.push_back(i);
}
solve(v, rng);
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
364 KB |
Output is correct |
| 2 |
Correct |
1 ms |
364 KB |
Output is correct |
| 3 |
Correct |
1 ms |
364 KB |
Output is correct |
| 4 |
Correct |
0 ms |
364 KB |
Output is correct |
| 5 |
Correct |
1 ms |
364 KB |
Output is correct |
| 6 |
Correct |
1 ms |
364 KB |
Output is correct |
| 7 |
Correct |
1 ms |
364 KB |
Output is correct |
| 8 |
Correct |
1 ms |
364 KB |
Output is correct |
| 9 |
Correct |
1 ms |
364 KB |
Output is correct |
| 10 |
Correct |
1 ms |
364 KB |
Output is correct |
| 11 |
Correct |
1 ms |
364 KB |
Output is correct |
| 12 |
Correct |
1 ms |
364 KB |
Output is correct |
| 13 |
Correct |
1 ms |
364 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
364 KB |
Output is correct |
| 2 |
Correct |
1 ms |
364 KB |
Output is correct |
| 3 |
Correct |
1 ms |
364 KB |
Output is correct |
| 4 |
Correct |
0 ms |
364 KB |
Output is correct |
| 5 |
Correct |
1 ms |
364 KB |
Output is correct |
| 6 |
Correct |
1 ms |
364 KB |
Output is correct |
| 7 |
Correct |
1 ms |
364 KB |
Output is correct |
| 8 |
Correct |
1 ms |
364 KB |
Output is correct |
| 9 |
Correct |
1 ms |
364 KB |
Output is correct |
| 10 |
Correct |
1 ms |
364 KB |
Output is correct |
| 11 |
Correct |
1 ms |
364 KB |
Output is correct |
| 12 |
Correct |
1 ms |
364 KB |
Output is correct |
| 13 |
Correct |
1 ms |
364 KB |
Output is correct |
| 14 |
Correct |
1 ms |
492 KB |
Output is correct |
| 15 |
Correct |
1 ms |
492 KB |
Output is correct |
| 16 |
Runtime error |
297 ms |
262148 KB |
Execution killed with signal 9 |
| 17 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
364 KB |
Output is correct |
| 2 |
Correct |
1 ms |
364 KB |
Output is correct |
| 3 |
Correct |
1 ms |
364 KB |
Output is correct |
| 4 |
Correct |
0 ms |
364 KB |
Output is correct |
| 5 |
Correct |
1 ms |
364 KB |
Output is correct |
| 6 |
Correct |
1 ms |
364 KB |
Output is correct |
| 7 |
Correct |
1 ms |
364 KB |
Output is correct |
| 8 |
Correct |
1 ms |
364 KB |
Output is correct |
| 9 |
Correct |
1 ms |
364 KB |
Output is correct |
| 10 |
Correct |
1 ms |
364 KB |
Output is correct |
| 11 |
Correct |
1 ms |
364 KB |
Output is correct |
| 12 |
Correct |
1 ms |
364 KB |
Output is correct |
| 13 |
Correct |
1 ms |
364 KB |
Output is correct |
| 14 |
Correct |
1 ms |
492 KB |
Output is correct |
| 15 |
Correct |
1 ms |
492 KB |
Output is correct |
| 16 |
Runtime error |
297 ms |
262148 KB |
Execution killed with signal 9 |
| 17 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
757 ms |
1496 KB |
Output is correct |
| 2 |
Correct |
911 ms |
1632 KB |
Output is correct |
| 3 |
Correct |
974 ms |
1572 KB |
Output is correct |
| 4 |
Correct |
908 ms |
1580 KB |
Output is correct |
| 5 |
Correct |
758 ms |
1600 KB |
Output is correct |
| 6 |
Correct |
819 ms |
1516 KB |
Output is correct |
| 7 |
Correct |
910 ms |
1736 KB |
Output is correct |
| 8 |
Correct |
1006 ms |
2268 KB |
Output is correct |
| 9 |
Correct |
998 ms |
2092 KB |
Output is correct |
| 10 |
Runtime error |
258 ms |
262148 KB |
Execution killed with signal 9 |
| 11 |
Halted |
0 ms |
0 KB |
- |
