Submission #341669

#TimeUsernameProblemLanguageResultExecution timeMemory
341669vonatlusGift (IZhO18_nicegift)C++17
30 / 100
2096 ms149788 KiB
/// wa #pragma GCC optimize("O3") //#pragma comment(linker, "/STACK:36777216") #include<bits/stdc++.h> #define x first #define y second #define pb push_back #define sz(x) (int) x.size() #define all(z) (z).begin(), (z).end() using namespace std; using ll = long long; using pii = pair<ll, int>; const int MOD = 1e9 + 7; const int INF = 1e9 + 1e2; //mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); void fin() { #ifdef AM freopen(".in", "r", stdin); #endif } const bool flag = 0; const int N = 1e6+10; pii t[N<<2]; ll a[N], n; void build(int u = 0, int l = 0, int r = n) { if (r-l == 1) { t[u] = {a[l], l}; return; } int m = l+r >> 1; build(u+u+1, l, m); build(u+u+2, m, r); t[u] = max(t[u+u+1], t[u+u+2]); } void modify(int pos, ll val, int u = 0, int l = 0, int r = n) { if (r-l == 1) { t[u].x = val; return; } int m = l+r >> 1; if (pos < m) { modify(pos, val, u+u+1, l, m); } else { modify(pos, val, u+u+2, m, r); } t[u] = max(t[u+u+1], t[u+u+2]); } void ma1n() { int k; cin >> n >> k; ll sum = 0; for (int i = 0; i < n; ++i) { cin >> a[i], sum += a[i]; } build(); vector<vector<int>> ans; while (1) { if (t[0].x == 0) break; vector<int> p; vector<pii> v; for (int i = 0; i < k; ++i) { p.pb(t[0].y+1); if (t[0].x == 0) { cout << -1, exit(0); } v.pb({t[0].y, t[0].x}); modify(t[0].y, 0); } ll d = v.back().y-t[0].x+1; if (t[0].x == 0) d--; p.insert(p.begin(), d); for (pii x : v) { modify(x.x, x.y-d); } ans.pb(p); } if (sz(ans) * 1ll * k > 3e6) cout << -1, exit(0); cout << sz(ans) << "\n"; for (vector<int>& p : ans) { for (int x : p) cout << x << " "; cout << "\n"; } } int main() { ios_base::sync_with_stdio(0); cin.tie(nullptr), fin(); int ts = 1; if (flag) { cin >> ts; } while (ts--) { ma1n(); } return 0; }

Compilation message (stderr)

nicegift.cpp: In function 'void build(int, int, int)':
nicegift.cpp:43:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   43 |     int m = l+r >> 1;
      |             ~^~
nicegift.cpp: In function 'void modify(int, ll, int, int, int)':
nicegift.cpp:54:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   54 |     int m = l+r >> 1;
      |             ~^~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...