Submission #1048891

#TimeUsernameProblemLanguageResultExecution timeMemory
1048891GrindMachineMinerals (JOI19_minerals)C++17
75 / 100
101 ms3860 KiB
#include <bits/stdc++.h> #include <ext/pb_ds/assoc_container.hpp> #include <ext/pb_ds/tree_policy.hpp> using namespace std; using namespace __gnu_pbds; template<typename T> using Tree = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>; typedef long long int ll; typedef long double ld; typedef pair<int,int> pii; typedef pair<ll,ll> pll; #define fastio ios_base::sync_with_stdio(false); cin.tie(NULL) #define pb push_back #define endl '\n' #define sz(a) (int)a.size() #define setbits(x) __builtin_popcountll(x) #define ff first #define ss second #define conts continue #define ceil2(x,y) ((x+y-1)/(y)) #define all(a) a.begin(), a.end() #define rall(a) a.rbegin(), a.rend() #define yes cout << "Yes" << endl #define no cout << "No" << endl #define rep(i,n) for(int i = 0; i < n; ++i) #define rep1(i,n) for(int i = 1; i <= n; ++i) #define rev(i,s,e) for(int i = s; i >= e; --i) #define trav(i,a) for(auto &i : a) template<typename T> void amin(T &a, T b) { a = min(a,b); } template<typename T> void amax(T &a, T b) { a = max(a,b); } #ifdef LOCAL #include "debug.h" #else #define debug(...) 42 #endif /* refs: some other solutions */ const int MOD = 1e9 + 7; const int N = 1e5 + 5; const int inf1 = int(1e9) + 5; const ll inf2 = ll(1e18) + 5; #include "minerals.h" vector<pii> ans; vector<int> best(N); void precalc(int n){ vector<int> dp(n+5,inf1); dp[1] = 0; for(int i = 2; i <= n; ++i){ if(i <= 1000){ rep1(j,i/2){ int val = dp[j]+dp[i-j]+i+j-1; if(val < dp[i]){ dp[i] = val; best[i] = j; } } } else{ for(int j = i/3-5; j <= i/2; ++j){ int val = dp[j]+dp[i-j]+i+j-1; if(val < dp[i]){ dp[i] = val; best[i] = j; } } } } } void go(vector<int> &a, vector<int> &b, ll t){ if(a.empty()) return; if(sz(a) == 1){ ans.pb({a[0],b[0]}); return; } int mid1 = best[sz(a)]; int mid2 = sz(a)-mid1; vector<int> al,ar; int d = 0; if(!t){ rep(i,sz(a)){ if(i < mid1){ al.pb(a[i]); d = Query(a[i]); } else{ ar.pb(a[i]); } } } else{ rep(i,sz(a)){ if(i < mid2){ al.pb(a[i]); } else{ ar.pb(a[i]); d = Query(a[i]); } } } vector<int> bl,br; rep(i,sz(b)-1){ int x = b[i]; int res = Query(x); if(res == d){ bl.pb(x); } else{ br.pb(x); } d = res; } int x = b.back(); if(sz(al) != sz(bl)) bl.pb(x); else br.pb(x); go(al,bl,1); go(ar,br,0); } void Solve(int n) { // int v = Query(1); // for (int i = 1; i <= N; ++i) { // Answer(i, 2 * N + 1 - i); // } precalc(n); vector<int> v1,v2; int distinct = 0; rep1(i,2*n){ int x = Query(i); if(x == distinct+1){ v1.pb(i); distinct++; } else{ v2.pb(i); } } rep1(i,2*n) Query(i); go(v1,v2,0); for(auto [i,j] : ans){ Answer(i,j); } }
#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...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...