#include <bits/stdc++.h>
//#pragma GCC optimize("unroll-loops")
//#pragma GCC optimize("-O3")
//#pragma GCC optimize("Ofast")
#define F first
#define S second
#define sz(x) int(x.size())
#define pb push_back
#define N 500005
#define M ll(1e9 + 7)
#define inf 1e9 + 1e9
using namespace std;
typedef long double ld;
typedef long long ll;
typedef short int si;
bool cmp(pair <pair <int, int>, int> x, pair <pair <int, int>, int> y)
{
if (x.F.F != y.F.F) return x.F.F > y.F.F;
return x.F.S > y.F.S;
}
set <int> gt[N];
int main()
{
// freopen("input.txt", "r", stdin);// freopen("output.txt", "w", stdout);
ios_base::sync_with_stdio(0); istream::sync_with_stdio(0); cin.tie(0); cout.tie(0);
int n, m;
cin >> m >> n;
int obr[n];
vector <pair <pair <int, int>, int> > g; g.resize(n);
for (int i = 0; i < n; i++) {cin >> g[i].F.F >> g[i].F.S; g[i].S = i;}
vector <pair <int, pair <int, int> > > vr; vr.clear();
sort(g.begin(), g.end(), cmp);
for (int i = 0; i < n; i++) obr[g[i].S] = i;
int a[6];
set <int> st; st.clear();
set <pair <int, int> > se; se.clear();
for (int i = 0; i < 6; i++) {a[i] = g[i].S; se.insert({g[i].F.S, g[i].S}); st.insert(g[i].S);}
int j = 6, pos = 0;
vector <pair <int, int> > gr; gr.clear();
vector <pair <int, int> > ost; ost.clear();
set <pair <int, int> > dob; dob.clear();
for (int i = 1; i <= m; i++)
{
for (auto it : st) gt[it].insert(i);
if (i == m) break;
vector <int> gr; gr.clear();
while (sz(se) > 0 && (*se.begin()).F == i)
{
gr.pb((*se.begin()).S);
for (auto it : gt[gr.back()]) dob.insert({it, gr.back()});
se.erase(se.begin());
st.erase(gr.back());
}
while (sz(gr) > 0 && j < sz(g))
{
if (sz(dob) && pos < sz(ost))
{
int tm = (*dob.begin()).F, nm = (*dob.begin()).S;
dob.erase(dob.begin());
ost[pos].F--;
st.insert(nm);
se.insert({i + 1, nm});
gr.pop_back();
gt[ost[pos].S].insert(tm);
gt[nm].erase(tm);
if (ost[pos].F == 0) pos++;
continue;
}
se.insert({i + g[j].F.S, g[j].S});
st.insert(g[j].S);
int ostr = max(0, (i + g[j].F.S) - m);
if (ostr > 0) ost.pb({ostr, g[j].S});
gr.pop_back();
j++;
}
}
ll ans = 0;
vector <int> tmr[m + 1];
for (int i = 0; i <= m; i++) tmr[i].clear();
for (int i = 0; i < n; i++)
for (auto it : gt[i]) {tmr[it].pb(i); ans += g[obr[i]].F.F;}
cout << ans << endl;
for (int i = 0; i < 6; i++) a[i] = tmr[1][i];
sort(a, a + 6);
vector <int> pr; pr.clear();
for (int i = 0; i < 6; i++) {pr.pb(a[i]); cout << a[i] + 1 << " "; } cout << endl;
for (int i = 2; i <= m; i++)
{
sort(pr.begin(), pr.end());
vector <int> grr = tmr[i];
sort(grr.begin(), grr.end());
vector <int> nw; nw.clear();
int j = 0;
while (j < sz(pr))
{
if (pr[j] == grr[j]) nw.pb(pr[j]);
else
{
nw.pb(grr[j]);
vr.pb({i, {pr[j], grr[j]}});
}
j++;
}
pr = nw;
}
cout << sz(vr) << endl;
for (auto it : vr) cout << it.F << " " << it.S.F + 1 << " " << it.S.S + 1 << '\n';
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
21 ms |
23808 KB |
Output isn't correct |
2 |
Incorrect |
32 ms |
25800 KB |
Output isn't correct |
3 |
Runtime error |
215 ms |
65540 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
4 |
Incorrect |
27 ms |
25216 KB |
Output isn't correct |
5 |
Runtime error |
161 ms |
65540 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
6 |
Incorrect |
24 ms |
24192 KB |
Output isn't correct |
7 |
Incorrect |
29 ms |
24832 KB |
Output isn't correct |
8 |
Incorrect |
367 ms |
52332 KB |
Output isn't correct |
9 |
Runtime error |
1012 ms |
65540 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |
10 |
Runtime error |
322 ms |
65536 KB |
Execution killed with signal 9 (could be triggered by violating memory limits) |