Submission #318393

#TimeUsernameProblemLanguageResultExecution timeMemory
318393ant101Vrtić (COCI18_vrtic)C++14
80 / 160
99 ms82276 KiB
#include <iostream> #include <algorithm> #include <cstring> #include <iomanip> #include <fstream> #include <cmath> #include <vector> #include <set> #include <unordered_set> #include <unordered_map> #include <map> #include <stack> #include <queue> #include <assert.h> #include <limits> #include <cstdio> #include <complex> using namespace std; typedef long long ll; typedef long double ld; typedef double db; typedef string str; typedef pair<int, int> pi; typedef pair<ll,ll> pl; typedef pair<ld,ld> pd; #define mp make_pair #define f first #define s second typedef vector<int> vi; typedef vector<ll> vl; typedef vector<ld> vd; typedef vector<str> vs; typedef vector<pi> vpi; typedef vector<pl> vpl; typedef vector<pd> vpd; #define sz(x) (int)x.size() #define all(x) begin(x), end(x) #define rall(x) (x).rbegin(), (x).rend() #define rsz resize #define ins insert #define ft front() #define bk back() #define pf push_front #define pb push_back #define eb emplace_back #define lb lower_bound #define ub upper_bound #define FOR(i,a,b) for (int i = (a); i < (b); ++i) #define F0R(i,a) FOR(i,0,a) #define ROF(i,a,b) for (int i = (b)-1; i >= (a); --i) #define R0F(i,a) ROF(i,0,a) #define trav(a,x) for (auto& a: x) const int MOD = 1e9+7; // 998244353; // = (119<<23)+1 const int MX = 2e2+5; const ll INF = 1e18; const ld PI = 4*atan((ld)1); const int dx[4] = {0,1,0,-1}, dy[4] = {1,0,-1,0}; namespace io { void setIn(string s) { freopen(s.c_str(),"r",stdin); } void setOut(string s) { freopen(s.c_str(),"w",stdout); } void setIO(string s = "") { ios_base::sync_with_stdio(0); cin.tie(0); // fast I/O // cin.exceptions(cin.failbit); // ex. throws exception when you try to read letter into int if (sz(s)) { setIn(s+".in"); setOut(s+".out"); } // for USACO } } using namespace io; namespace input { template<class T> void re(complex<T>& x); template<class T1, class T2> void re(pair<T1,T2>& p); template<class T> void re(vector<T>& a); template<class T, size_t SZ> void re(array<T,SZ>& a); template<class T> void re(T& x) { cin >> x; } void re(double& x) { string t; re(t); x = stod(t); } void re(ld& x) { string t; re(t); x = stold(t); } template<class Arg, class... Args> void re(Arg& first, Args&... rest) { re(first); re(rest...); } template<class T> void re(complex<T>& x) { T a,b; re(a,b); x = cd(a,b); } template<class T1, class T2> void re(pair<T1,T2>& p) { re(p.f,p.s); } template<class T> void re(vector<T>& a) { F0R(i,sz(a)) re(a[i]); } template<class T, size_t SZ> void re(array<T,SZ>& a) { F0R(i,SZ) re(a[i]); } } namespace output { template<class T1, class T2> void pr(const pair<T1,T2>& x); template<class T, size_t SZ> void pr(const array<T,SZ>& x); template<class T> void pr(const vector<T>& x); template<class T> void pr(const set<T>& x); template<class T1, class T2> void pr(const map<T1,T2>& x); template<class T> void pr(const T& x) { cout << x; } template<class Arg, class... Args> void pr(const Arg& first, const Args&... rest) { pr(first); pr(rest...); } template<class T1, class T2> void pr(const pair<T1,T2>& x) { pr("{",x.f,", ",x.s,"}"); } template<class T> void prContain(const T& x) { pr("{"); bool fst = 1; for (const auto& a: x) pr(!fst?", ":"",a), fst = 0; // const needed for vector<bool> pr("}"); } template<class T, size_t SZ> void pr(const array<T,SZ>& x) { prContain(x); } template<class T> void pr(const vector<T>& x) { prContain(x); } template<class T> void pr(const set<T>& x) { prContain(x); } template<class T1, class T2> void pr(const map<T1,T2>& x) { prContain(x); } void ps() { pr("\n"); } template<class Arg> void ps(const Arg& first) { pr(first); ps(); // no space at end of line } template<class Arg, class... Args> void ps(const Arg& first, const Args&... rest) { pr(first," "); ps(rest...); // print w/ spaces } } using namespace output; using namespace input; ll add(ll a, ll b) { a += b; if(a >= MOD) { a -= MOD; } return a; } ll sub(ll a, ll b) { a -= b; if(a < 0) { a += MOD; } return a; } ll mul(ll a, ll b) { return (a * b)%MOD; } void add_self(ll& a, ll b) { a = add(a, b); } void sub_self(ll& a, ll b) { a = sub(a, b); } void mul_self(ll& a, ll b) { a = mul(a, b); } ll b = 13; ll ppow[MX]; ll N; map<ll, pl> getstate; ll dp[4230154]; vl adj[MX]; ll cntcycles[MX]; ll bags[MX]; ll ans[MX][MX]; pl cl[MX]; bool visited[MX]; ll curr = 0; ll cs = 0; map<ll, pl> progression; map<ll, vl> sloc; ll finalans[MX]; ll currbag = 1; ll toadd = 2, minval, maxval; void assignans(ll u, ll p, ll s) { finalans[u] = bags[currbag]; currbag+=toadd; if (toadd == 2) { if (currbag == maxval-1) { toadd = 1; } else if (currbag == maxval) { toadd = -1; } } else if (toadd == -1 || toadd == 1) { toadd = -2; } visited[u] = true; trav (v, adj[u]) { if (v != s) { assignans(v, u, s); } } } ll getcycles(ll u, ll p, ll s) { visited[u] = true; trav (v, adj[u]) { if (v != s) { return 1+getcycles(v, u, s); } } return 1; } void findstates(ll i, ll currhash, ll amnt) { if (i == curr) { getstate[currhash] = {cs++, amnt}; return; } F0R (j, cl[i].s+1) { findstates(i+1, add(currhash, j*cl[i].f*ppow[i]), amnt+j*cl[i].f); } } ll f(ll i) { if (getstate[i].s == N) { return 0; } if (dp[i] != -1) { return dp[i]; } ll currind = getstate[i].s+1; dp[i] = 1e13; F0R (j, curr) { ll newhash = add(i, cl[j].f*ppow[j]); if (getstate.count(newhash)) { ll val = max(ans[currind][currind+cl[j].f-1], f(newhash)); if (val < dp[i]) { dp[i] = val; progression[i] = {newhash, cl[j].f}; } } } // ps(i, dp[i]); return dp[i]; } int main() { setIO(); memset(dp, -1, sizeof(dp)); ppow[0] = 1; re(N); FOR (i, 1, N+1) { ppow[i] = mul(ppow[i-1], b); } FOR (i, 1, N+1) { ll a; re(a); adj[i].pb(a); } FOR (i, 1, N+1) { re(bags[i]); } sort(bags+1, bags+1+N); FOR (i, 1, N+1) { ans[i][i] = 0; FOR (j, i+1, N+1) { for (ll k = i; k<=j-2; k+=2) { ans[i][j] = max(ans[i][j], abs(bags[k]-bags[k+2])); } ans[i][j] = max(ans[i][j], abs(bags[j]-bags[j-1])); for (ll k = ((j-i)%2 == 0 ? j-1 : j); k>i+1; k-=2) { ans[i][j] = max(ans[i][j], abs(bags[k]-bags[k-2])); } ans[i][j] = max(ans[i][j], abs(bags[i]-bags[i+1])); } } FOR (i, 1, N+1) { if (!visited[i]) { ll val = getcycles(i, -1, i); cntcycles[val]++; if (cntcycles[val] > 1) { sloc[val].pb(i); } else { sloc[val] = {i}; } } } FOR (i, 1, N+1) { if (cntcycles[i]) cl[curr++] = {i, cntcycles[i]}; } findstates(0, 0, 0); ps(f(0)); ll pepega = 0; ll currmin = 1; while (getstate[pepega].s != N) { minval = currmin; currbag = minval; maxval = currmin+progression[pepega].s-1; toadd = min(2ll, maxval-minval); assignans(sloc[progression[pepega].s][sz(sloc[progression[pepega].s])-1], -1, sloc[progression[pepega].s][sz(sloc[progression[pepega].s])-1]); sloc[progression[pepega].s].pop_back(); currmin+=progression[pepega].s; pepega = progression[pepega].f; } FOR (i, 1, N) { cout << finalans[i] << " "; } cout << finalans[N] << "\n"; return 0; }

Compilation message (stderr)

vrtic.cpp: In function 'void io::setIn(std::string)':
vrtic.cpp:67:35: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   67 |     void setIn(string s) { freopen(s.c_str(),"r",stdin); }
      |                            ~~~~~~~^~~~~~~~~~~~~~~~~~~~~
vrtic.cpp: In function 'void io::setOut(std::string)':
vrtic.cpp:68:36: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
   68 |     void setOut(string s) { freopen(s.c_str(),"w",stdout); }
      |                             ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
#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...
#Verdict Execution timeMemoryGrader output
Fetching results...