QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#196396 | #6886. Simple Set Problem | Royo# | AC ✓ | 1228ms | 58556kb | C++20 | 1.8kb | 2023-10-01 16:49:49 | 2023-10-01 16:49:50 |
Judging History
answer
#include <bits/stdc++.h>
#include <cstdio>
//#define int long long
#define PII pair<int, int>
#pragma GCC optimize("Ofast")
#define NO {puts("No") ; return ;}
#define YES {puts("Yes") ; return ;}
#define pb push_back
#define endl "\n"
#define fi first
#define se second
#define IOS std::ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
using namespace std;
mt19937 rd(time(0));
const int N = 1e5 + 10;
void solve() {
int n; cin >> n;
vector<PII> v;
for (int i = 1; i <= n; i++)
{
int k; cin >> k;
for (int j = 1; j <= k; j++)
{
int x; cin >> x;
v.pb({x, i});
}
}
//exit(0);
sort(v.begin(), v.end());
//for (auto it : v) cout << it.fi << ' ' << it.se << endl;
if (n == 1)
{
cout << 0 << endl;
return;
}
map<int, int> q;
int kind = 0;
int ans = 1e17;
//cout << endl;
int r = 0;
int ma = 0;
for (int l = 0; l < v.size() - n + 1; l++)
{
int c = v[l].fi, ver = v[l].se;
if (kind == n)
{
//cout << ver << ' ' << ver1 << endl;
//cout << c << ' ' << ma << endl;
ans = min(ma - c, ans);
}
while (kind != n && r < v.size())
{
int c1 = v[r].fi, ver1 = v[r].se;
if (q[ver1] != 0) q[ver1]++, r++;
else
{
q[ver1]++; kind++;
r++;
ma = c1;
}
if (kind == n)
{
//cout << ver << ' ' << ver1 << endl;
//cout << c << ' ' << ma << endl;
ans = min(ma - c, ans);
break;
}
}
//cout << q[3] << endl;
// q[ver]++;
// if (q[ver] == 1) kind++;
//if (kind == n) ans = min(ma - c, ans);
q[ver]--;
//if (ver == 3) cout << q[ver] << "!!!!" << endl;
if (q[ver] == 0) kind--;
}
cout << ans << endl;
}
signed main() {
IOS;
int t; cin >> t;
while (t -- )
solve();
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 1228ms
memory: 58556kb
input:
10018 1 5 -247462786 -97914904 849160785 -951926514 -829935728 7 72 8382969 -3251289 -63130380 -590108505 -798189380 -140833313 -626464256 136468139 -711222365 500861930 -459837972 914918723 186793042 872925162 -335485808 641571163 -314777234 -520573290 -894124702 618889116 2700292 -714868427 -34346...
output:
0 1800402714 860165806 487641037 229279918 238532335 392707612 456994871 256099628 1023121975 4986247 753213024 0 1289600751 598093746 55025093 95257568 145430738 34342513 0 157895624 789721360 232287715 1817496622 439049782 777966568 29118927 1671939338 1048279188 42073227 642353647 61747459 302989...
result:
ok 10018 lines