//Konrad Paluszek,University of Warsaw(former XIV LO Staszic) //#STAY AT HOME #ifndef LOCAL #pragma GCC optimize("O3") #endif #define TIME (chrono::steady_clock::now().time_since_epoch().count()) #include<bits/stdc++.h> #include<ext/pb_ds/assoc_container.hpp> #include<ext/pb_ds/tree_policy.hpp> #define xfm(a,b)a##b #define xwb(a,b)xfm(a,b) #define _ xwb(nvj,__LINE__) #define __ xwb(kjy,__LINE__) #define ___ xwb(cjm,__LINE__) #define REP(i,n)for(urs(n)i=0;i<(n);++i) #define PER(r...)for(bool _=1;_||next_permutation(r);_=false) #define FS(r)r.first,r.second #define ALL(r)(r).begin(),(r).end() #define M0(r) memset(r,0,sizeof(r)) #define sim template<class c #define forbits(i,m)if(m)for(urs(m)i=ctz(m),i##nvj=m;i##nvj;i##nvj^=((urs(m))1<<i),i=i##nvj?ctz(i##nvj):0) #define fordbits(i,m)if(m)for(urs(m)i=8*sizeof(m)-clz(m)-1,i##nxd=m;i##nxd;i##nxd^=((urs(m))1<<i),i=i##nxd?8*sizeof(m)-clz(i##nxd)-1:0) #define ksets(t, m, k, n)for(t m=(((t)1<<(k))-1);m<((t)1<<(n));m=nux(m)) #define urs(r...)typename decay<decltype(r)>::type #define hur(f,g)sim>int f(c a){if(sizeof(c)==8)return g##ll(a);return g(a);} using namespace __gnu_pbds;using namespace std;using ll=long long;using ld=long double;using ull=unsigned long long;using vi=vector<int>;using vll=vector<ll>;using pii=pair<int,int>;using pll=pair<ll,ll>;using vpii=vector<pii>;using unt=unsigned int;sim>using min_queue=priority_queue<c,vector<c>,greater<>>;sim,class b,class cmp=less<c>>using ordered_map=tree<c,b,cmp,rb_tree_tag,tree_order_statistics_node_update>;sim,class cmp=less<c>>using ordered_set=ordered_map<c,null_type,cmp>;hur(popc,__builtin_popcount)hur(ctz,__builtin_ctz)hur(clz,__builtin_clz)sim,class N>bool mini(c&o,const N&h){if(o>h)return o=h,1;return 0;}sim,class N>bool maxi(c&o,const N&h){if(o<h)return o=h,1;return 0;} #ifdef LOCAL #include </home/konrad/cp/headers/debuglib.hpp> #else #define loc(...) #define onl(r...)r #define debug(...) #define print_stack(...) #define mark_stack(...) #define set_pre(...) #define reg_it(...) #define def_op(...) struct _{}; #define mask_set(...) #define exit my_exit void __resources(); void my_exit(int x) {fflush(stdout); #ifdef LOCAL2 __resources(); #endif _Exit(x);} #endif #define next nexT #define prev preV #define tree trEE #define left lefT #define right righT #define div diV #define y1 y_1 #define pow don't' ull mix(ull o){o+=0x9e3779b97f4a7c15;o=(o^(o>>30))*0xbf58476d1ce4e5b9;o=(o^(o>>27))*0x94d049bb133111eb;return o^(o>>31);}ull SALT=0x7a14a4b0881ebf9,tqu=0x7a14a4b0881ebf9;ull my_rand(){return tqu=mix(tqu);}void my_srand(ull x){SALT=tqu=x;}const int inf=1023400000;const ll llinf=1234567890000000000ll;ll fix(ll o, ll m){o%=m;if(o<0)o+=m;return o;} #define rand my_rand #define srand my_srand #define random_shuffle(r...)random_shuffle(r,[](int _){return my_rand()%_;}) sim>inline c nux(c m){if(!m)return numeric_limits<c>::max();c A=m&-m;c B=~((A-1)^m);c C=B&-B;c D=(C>>(1+ctz(A)))-1;return C|(m&~(C-1))|D;}sim>void unq(c&x){x.resize(unique(ALL(x))-x.begin());} //#STAY AT HOME int run(vpii which) { map <vpii, int> dist; queue<pair <vpii, int> > bfs; vi ans(which[2].second + 1, -1); auto touch = [&](const vpii &a, int d) { auto [_, added] = dist.insert(make_pair(a, d)); for (auto [x, _] : a) { if (x < (int) ans.size() && ans[x] == -1) ans[x] = d; } if (added) bfs.emplace(a, d); }; touch(which, 0); while (!bfs.empty()) { auto [b, d] = bfs.front(); bfs.pop(); // debug(imie(b), imie(d)); REP(i, 3) REP(j, 3) if (i != j) { int move = min(b[i].first, b[j].second - b[j].first); vpii b2 = b; b2[i].first -= move; b2[j].first += move; touch(b2, d + 1); } } int s = dist.size(); for (int c : ans) printf("%d ", c); puts(""); return s; } int losuj(int a, int b) { return a + rand() % (b - a + 1); } void test() { int M; scanf("%d", &M); int best = 0; int did = 0; while (true) { did++; vpii x(3); for (auto &[a, b] : x) { b = losuj(1, M); a = losuj(0, b); } int g = run(x); if (g > best) { best = g; debug(imie(g), imie(x)); } if (did % 10000 == 0) debug(imie(did)); } } int main() { // test(); // return 0; vpii x(3); for (auto &[_, a] : x) scanf("%d", &a); for (auto &[a, _] : x) scanf("%d", &a); run(x); exit(0); } //#STAY AT HOME
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 | //Konrad Paluszek,University of Warsaw(former XIV LO Staszic) //#STAY AT HOME #ifndef LOCAL #pragma GCC optimize("O3") #endif #define TIME (chrono::steady_clock::now().time_since_epoch().count()) #include<bits/stdc++.h> #include<ext/pb_ds/assoc_container.hpp> #include<ext/pb_ds/tree_policy.hpp> #define xfm(a,b)a##b #define xwb(a,b)xfm(a,b) #define _ xwb(nvj,__LINE__) #define __ xwb(kjy,__LINE__) #define ___ xwb(cjm,__LINE__) #define REP(i,n)for(urs(n)i=0;i<(n);++i) #define PER(r...)for(bool _=1;_||next_permutation(r);_=false) #define FS(r)r.first,r.second #define ALL(r)(r).begin(),(r).end() #define M0(r) memset(r,0,sizeof(r)) #define sim template<class c #define forbits(i,m)if(m)for(urs(m)i=ctz(m),i##nvj=m;i##nvj;i##nvj^=((urs(m))1<<i),i=i##nvj?ctz(i##nvj):0) #define fordbits(i,m)if(m)for(urs(m)i=8*sizeof(m)-clz(m)-1,i##nxd=m;i##nxd;i##nxd^=((urs(m))1<<i),i=i##nxd?8*sizeof(m)-clz(i##nxd)-1:0) #define ksets(t, m, k, n)for(t m=(((t)1<<(k))-1);m<((t)1<<(n));m=nux(m)) #define urs(r...)typename decay<decltype(r)>::type #define hur(f,g)sim>int f(c a){if(sizeof(c)==8)return g##ll(a);return g(a);} using namespace __gnu_pbds;using namespace std;using ll=long long;using ld=long double;using ull=unsigned long long;using vi=vector<int>;using vll=vector<ll>;using pii=pair<int,int>;using pll=pair<ll,ll>;using vpii=vector<pii>;using unt=unsigned int;sim>using min_queue=priority_queue<c,vector<c>,greater<>>;sim,class b,class cmp=less<c>>using ordered_map=tree<c,b,cmp,rb_tree_tag,tree_order_statistics_node_update>;sim,class cmp=less<c>>using ordered_set=ordered_map<c,null_type,cmp>;hur(popc,__builtin_popcount)hur(ctz,__builtin_ctz)hur(clz,__builtin_clz)sim,class N>bool mini(c&o,const N&h){if(o>h)return o=h,1;return 0;}sim,class N>bool maxi(c&o,const N&h){if(o<h)return o=h,1;return 0;} #ifdef LOCAL #include </home/konrad/cp/headers/debuglib.hpp> #else #define loc(...) #define onl(r...)r #define debug(...) #define print_stack(...) #define mark_stack(...) #define set_pre(...) #define reg_it(...) #define def_op(...) struct _{}; #define mask_set(...) #define exit my_exit void __resources(); void my_exit(int x) {fflush(stdout); #ifdef LOCAL2 __resources(); #endif _Exit(x);} #endif #define next nexT #define prev preV #define tree trEE #define left lefT #define right righT #define div diV #define y1 y_1 #define pow don't' ull mix(ull o){o+=0x9e3779b97f4a7c15;o=(o^(o>>30))*0xbf58476d1ce4e5b9;o=(o^(o>>27))*0x94d049bb133111eb;return o^(o>>31);}ull SALT=0x7a14a4b0881ebf9,tqu=0x7a14a4b0881ebf9;ull my_rand(){return tqu=mix(tqu);}void my_srand(ull x){SALT=tqu=x;}const int inf=1023400000;const ll llinf=1234567890000000000ll;ll fix(ll o, ll m){o%=m;if(o<0)o+=m;return o;} #define rand my_rand #define srand my_srand #define random_shuffle(r...)random_shuffle(r,[](int _){return my_rand()%_;}) sim>inline c nux(c m){if(!m)return numeric_limits<c>::max();c A=m&-m;c B=~((A-1)^m);c C=B&-B;c D=(C>>(1+ctz(A)))-1;return C|(m&~(C-1))|D;}sim>void unq(c&x){x.resize(unique(ALL(x))-x.begin());} //#STAY AT HOME int run(vpii which) { map <vpii, int> dist; queue<pair <vpii, int> > bfs; vi ans(which[2].second + 1, -1); auto touch = [&](const vpii &a, int d) { auto [_, added] = dist.insert(make_pair(a, d)); for (auto [x, _] : a) { if (x < (int) ans.size() && ans[x] == -1) ans[x] = d; } if (added) bfs.emplace(a, d); }; touch(which, 0); while (!bfs.empty()) { auto [b, d] = bfs.front(); bfs.pop(); // debug(imie(b), imie(d)); REP(i, 3) REP(j, 3) if (i != j) { int move = min(b[i].first, b[j].second - b[j].first); vpii b2 = b; b2[i].first -= move; b2[j].first += move; touch(b2, d + 1); } } int s = dist.size(); for (int c : ans) printf("%d ", c); puts(""); return s; } int losuj(int a, int b) { return a + rand() % (b - a + 1); } void test() { int M; scanf("%d", &M); int best = 0; int did = 0; while (true) { did++; vpii x(3); for (auto &[a, b] : x) { b = losuj(1, M); a = losuj(0, b); } int g = run(x); if (g > best) { best = g; debug(imie(g), imie(x)); } if (did % 10000 == 0) debug(imie(did)); } } int main() { // test(); // return 0; vpii x(3); for (auto &[_, a] : x) scanf("%d", &a); for (auto &[a, _] : x) scanf("%d", &a); run(x); exit(0); } //#STAY AT HOME |