API tools faq
paste
DuongNhi99

XOR3

DuongNhi99
Dec 13th, 2020
129
0
Never
Add comment
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 8.91 KB | None | 0 0
raw download clone embed print report
  1. //
  2. //  main.cpp
  3. //  xorcontest
  4. //
  5. //  Created by Trần Nam KhĂ¡nh on 11/25/20.
  6. //
  7.  
  8. #include <iostream>
  9. #include <cmath>
  10. using namespace std;
  11. long long a[3],b[3],dp[100][1ll<<3][1ll<<3];
  12. long long cal(long long ind,long long oka,long long okb)
  13. {
  14.     if(ind<0)return 0;
  15.     if(dp[ind][oka][okb]!=-1ll)return dp[ind][oka][okb];
  16.     long long res=0;
  17.     long long newoka=oka,newokb=okb,id[3];
  18.     for(long long i=0;i<(1ll<<3);i++)
  19.     {
  20.         newoka=oka;
  21.         newokb=okb;
  22.         long long cur=0;
  23.         for(long long j=0;j<=2;j++)
  24.         {
  25.             id[j]=((1ll<<j)&i)!=0;
  26.             cur^=id[j];
  27.         }
  28.         for(long long j=0;j<=2;j++)
  29.         {
  30.             long long sta=(oka&(1ll<<j))!=0;
  31.             long long stb=(okb&(1ll<<j))!=0;
  32.             long long ida=(a[j]&(1ll<<ind))!=0;
  33.             long long idb=(b[j]&(1ll<<ind))!=0;
  34.             if(sta==0&&id[j]<ida)
  35.             {
  36.                 newoka=-1ll;
  37.                 break;
  38.             }
  39.             if(stb==0&&id[j]>idb)
  40.             {
  41.                 newokb=-1ll;
  42.                 break;
  43.             }
  44.             long long tmp=(id[j]>ida);
  45.             newoka|=(tmp<<j);
  46.             tmp=(id[j]<idb);
  47.             newokb|=(tmp<<j);
  48.         }
  49.         if(newoka==-1ll||newokb==-1ll)continue;
  50.         res=max(res,cal(ind-1ll,newoka,newokb)+(cur<<ind));
  51.     }
  52.     return dp[ind][oka][okb]=res;
  53. }
  54. long long cal2(long long ind,long long oka,long long okb)
  55. {
  56.     if(ind<0)return 0;
  57.     if(dp[ind][oka][okb]!=-1ll)return dp[ind][oka][okb];
  58.     long long res=(long long)1e18;
  59.     long long newoka=oka,newokb=okb,id[3];
  60.     for(long long i=0;i<(1ll<<3);i++)
  61.     {
  62.         newoka=oka;
  63.         newokb=okb;
  64.         long long cur=0;
  65.         for(long long j=0;j<=2;j++)
  66.         {
  67.             id[j]=((1ll<<j)&i)!=0;
  68.             cur^=id[j];
  69.         }
  70.         for(long long j=0;j<=2;j++)
  71.         {
  72.             long long sta=(oka&(1ll<<j))!=0;
  73.             long long stb=(okb&(1ll<<j))!=0;
  74.             long long ida=(a[j]&(1ll<<ind))!=0;
  75.             long long idb=(b[j]&(1ll<<ind))!=0;
  76.             if(sta==0&&id[j]<ida)
  77.             {
  78.                 newoka=-1ll;
  79.                 break;
  80.             }
  81.             if(stb==0&&id[j]>idb)
  82.             {
  83.                 newokb=-1ll;
  84.                 break;
  85.             }
  86.             long long tmp=(id[j]>ida);
  87.             newoka|=(tmp<<j);
  88.             tmp=(id[j]<idb);
  89.             newokb|=(tmp<<j);
  90.         }
  91.         if(newoka==-1ll||newokb==-1ll)continue;
  92.         res=min(res,cal2(ind-1ll,newoka,newokb)+(cur<<ind));
  93.     }
  94.     return dp[ind][oka][okb]=res;
  95. }
  96. int main() {
  97.     ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
  98.     freopen("xor3.inp","r",stdin);
  99.     freopen("xor3.out","w",stdout);
  100.     long long l=0;
  101.     for(long long i=0;i<=2;i++)
  102.     {
  103.         cin>>a[i]>>b[i];
  104.         l=max(l,(long long)log2(b[i]));
  105.     }
  106.     for(long long i=0;i<=l;i++)
  107.     {
  108.         for(long long j=0;j<(1ll<<3);j++)
  109.         {
  110.             for(long long z=0;z<(1ll<<3);z++)
  111.             {
  112.                 dp[i][j][z]=-1ll;
  113.             }
  114.         }
  115.     }
  116.     cout<<cal2(l,0,0)<<endl;
  117.     for(long long i=0;i<=l;i++)
  118.     {
  119.         for(long long j=0;j<(1ll<<3);j++)
  120.         {
  121.             for(long long z=0;z<(1ll<<3);z++)
  122.             {
  123.                 dp[i][j][z]=-1ll;
  124.             }
  125.         }
  126.     }
  127.     cout<<cal(l,0,0)<<endl;
  128.     return 0;
  129. }
  130. #include <bits/stdc++.h>
  131.  
  132. #define task "XOR3"
  133. #define all(v) (v).begin(), (v).end()
  134. #define rep(i, l, r) for (int i = (l); i <= (r); ++i)
  135. #define Rep(i, r, l) for (int i = (r); i >= (l); --i)
  136. #define DB(X) { cerr << #X << " = " << (X) << '\n'; }
  137. #define DB1(A, _) { cerr << #A << "[" << _ << "] = " << (A[_]) << '\n'; }
  138. #define DB2(A, _, __) { cerr << #A << "[" << _ << "][" << __ << "] = " << (A[_][__]) << '\n'; }
  139. #define DB3(A, _, __, ___) { cerr << #A << "[" << _ << "][" << __ << "][" << ___ << "] = " << (A[_][__][___]) << '\n'; }
  140. #define PR(A, l, r) { cerr << '\n'; rep(_, l, r) DB1(A, _); cerr << '\n';}
  141. #define SZ(x) ((int)(x).size())
  142. #define pb push_back
  143. #define eb emplace_back
  144. #define pf push_front
  145. #define F first
  146. #define S second
  147. #define by(x) [](const auto& a, const auto& b) { return a.x < b.x; } // sort(arr, arr + N, by(a));
  148. #define next ___next
  149. #define prev ___prev
  150. #define y1 ___y1
  151. #define left ___left
  152. #define right ___right
  153. #define y0 ___y0
  154. #define div ___div
  155. #define j0 ___j0
  156. #define jn ___jn
  157.  
  158. using ll = long long;
  159. using ld = long double;
  160. using ull = unsigned long long;
  161. using namespace std;
  162. typedef pair<int, int> ii;
  163. typedef pair<ii, int> iii;
  164. typedef vector<int> vi;
  165. typedef vector<ii> vii;
  166. typedef vector<ll> vl;
  167. ll A[3], B[3], mem[51][2][2][2][2][2][2];
  168. ll dp(int pos, int grt0, int les0, int grt1, int les1, int grt2, int les2, bool ty)
  169. {
  170.     if (pos == 50)
  171.     {
  172.         if (ty) return ((grt0 && grt1 && grt2 && les0 && les1 && les2) ? 0 : -1e18);
  173.         else return ((grt0 && grt1 && grt2 && les0 && les1 && les2) ? 0 : 1e18);
  174.     }
  175.     ll &res = mem[pos][grt0][les0][grt1][les1][grt2][les2];
  176.     if (res != -1) return res;
  177.     res = (ty ? -1e18 : 1e18);
  178.     rep(i, 0, 1) rep(j, 0, 1) rep(k, 0, 1)
  179.     {
  180.         int ngrt0, nles0, ngrt1, nles1, ngrt2, nles2;
  181.         if (i > (A[0] >> pos & 1)) ngrt0 = 1;
  182.         else if (i < (A[0] >> pos & 1)) ngrt0 = 0;
  183.         else ngrt0 = grt0;
  184.         if (j > (A[1] >> pos & 1)) ngrt1 = 1;
  185.         else if (j < (A[1] >> pos & 1)) ngrt1 = 0;
  186.         else ngrt1 = grt1;
  187.         if (k > (A[2] >> pos & 1)) ngrt2 = 1;
  188.         else if (k < (A[2] >> pos & 1)) ngrt2 = 0;
  189.         else ngrt2 = grt2;
  190.         if (i < (B[0] >> pos & 1)) nles0 = 1;
  191.         else if (i > (B[0] >> pos & 1)) nles0 = 0;
  192.         else nles0 = les0;
  193.         if (j < (B[1] >> pos & 1)) nles1 = 1;
  194.         else if (j > (B[1] >> pos & 1)) nles1 = 0;
  195.         else nles1 = les1;
  196.         if (k < (B[2] >> pos & 1)) nles2 = 1;
  197.         else if (k > (B[2] >> pos & 1)) nles2 = 0;
  198.         else nles2 = les2;
  199.         if (ty) res = max(res, dp(pos + 1, ngrt0, nles0, ngrt1, nles1, ngrt2, nles2, 1) * 2 + (i ^ j ^ k));
  200.         else res = min(res, dp(pos + 1, ngrt0, nles0, ngrt1, nles1, ngrt2, nles2, 0) * 2 + (i ^ j ^ k));
  201.     }
  202.     if (res < 0) res = -1e18;
  203.     if (res > 1e15) res = 1e18;
  204.     return res;
  205.  
  206. }
  207. int main()
  208. {
  209.     freopen(task".inp", "r", stdin);
  210.     freopen(task".out", "w", stdout);
  211.     ios_base::sync_with_stdio(false); cin.tie(nullptr);
  212.     rep(i, 0, 2) cin >> A[i] >> B[i];
  213.     memset(mem, -1, sizeof(mem));
  214.     cout << dp(0, 1, 1, 1, 1, 1, 1, 0) << '\n';
  215.     memset(mem, -1, sizeof(mem));
  216.     cout << dp(0, 1, 1, 1, 1, 1, 1, 1);
  217.     return 0;
  218. }
  219. // Created by BJMinhNhut
  220. #include <bits/stdc++.h>
  221. using namespace std;
  222. #define all(x) (x).begin(), (x).end()
  223. #define rall(x) x.rbegin(), x.rend()
  224. #define pb push_back
  225. #define mp make_pair
  226. #define F first
  227. #define S second
  228. typedef int64_t ll;
  229. typedef vector<int> vi;
  230. typedef vector<ll> vll;
  231. void fast_io() {ios::sync_with_stdio(0); cin.tie(0);}
  232.  
  233. /***Main Code***/
  234. #define DEBUG 0
  235. #define FILE_IO 1
  236.  
  237. ll a[6];
  238. const int D = 60;
  239. const ll oo = 1e16;
  240. ll dp[D][100];
  241.  
  242. void Input() {
  243.     for(int i = 0; i < 6; ++i) cin >> a[i];
  244. }
  245.  
  246. bool getBit(ll t, ll i) {return (t>>i)&1;}
  247.  
  248. int check(int d, int st, int ok) {
  249.     int ok1 = 0;
  250.     for(int i = 0; i < 6; ++i) {
  251.         if (i%2 == 0) {
  252.  
  253.             if (getBit(ok, i)) ok1 ^= (1<<i);
  254.             else {
  255.                 if (getBit(a[i], d) < getBit(st, i>>1)) ok1 ^= (1<<i);
  256.                 if (getBit(a[i], d) > getBit(st, i>>1)) return -1;
  257.             }
  258.  
  259.         } else {
  260.  
  261.             if (getBit(ok, i)) ok1 ^= (1<<i);
  262.             else {
  263.                 if (getBit(a[i], d) > getBit(st, i>>1)) ok1 ^= (1<<i);
  264.                 if (getBit(a[i], d) < getBit(st, i>>1)) return -1;
  265.             }
  266.  
  267.         }
  268.     }
  269.     return ok1;
  270. }
  271.  
  272. ll getMin(ll i, int ok) {
  273.     if (i == -1) return 0;
  274.     ll &res = dp[i][ok];
  275.     if (res != -1) return res;
  276.  
  277.     res = oo;
  278.     for(int st = 0; st < (1<<3); ++st) {
  279.         int ok1 = check(i, st, ok);
  280.         if (ok1 == -1) continue;
  281.         ll d = __builtin_popcount(st)&1;
  282.         res = min(res, ll(d<<i) + getMin(i-1, ok1));
  283.     }
  284.     return res;
  285. }
  286.  
  287. ll getMax(ll i, int ok) {
  288.     if (i == -1) return 0;
  289.     ll &res = dp[i][ok];
  290.     if (res != -1) return res;
  291.  
  292.     res = 0;
  293.     for(int st = 0; st < (1<<3); ++st) {
  294.         int ok1 = check(i, st, ok);
  295.         if (ok1 == -1) continue;
  296.         ll d = __builtin_popcount(st)&1;
  297.         res = max(res, ll(d<<i) + getMax(i-1, ok1));
  298.     }
  299.     return res;
  300. }
  301.  
  302. void Solve() {
  303.     memset(dp, -1, sizeof dp);
  304.     cout << getMin(D-1, 0) << "\n";
  305.  
  306.     memset(dp, -1, sizeof dp);
  307.     cout << getMax(D-1, 0) << "\n";
  308. }
  309.  
  310. int main()
  311. {
  312.     fast_io();
  313.     if (FILE_IO) {
  314.         #define task "XOR3"
  315.         freopen(task".inp", "r", stdin);
  316.         freopen(task".out", "w", stdout);
  317.     }
  318.  
  319.     Input(), Solve();
  320.  
  321.     if (DEBUG) cout << "\nTime: " << clock()/1000.0 << "s";
  322.     return 0;
  323. }
Add Comment
Please, Sign In to add comment
Public Pastes
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy.  OK, I Understand
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!