fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #pragma GCC optimize("O3,unroll-loops")
  4. #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
  5. #define FOR(i, a, b) for (int i = (a); i <= (b); i++)
  6. #define FOD(i, a, b) for (int i = (a); i >= (b); i--)
  7. #define REP(i, n) for (int i = 1; i <= (n); i++)
  8. #define REP0(i, n) for (int i = 0; i < (n); i++)
  9. #define pb push_back
  10. #define printclock cerr << "\nTime : " << 1000 * (double)clock() / (double)CLOCKS_PER_SEC << "ms\n";
  11. const int mod = 1e9 + 7, inf = 1000111000, mxr = 305, mxn = 2e6 + 5;
  12. int adj[(int)3e5 + 5][7];
  13. int opp[7], n, r;
  14. bool dd[mxn];
  15. long long ans = 0;
  16. vector<int> bo;
  17. namespace sub125
  18. {
  19.     void solve()
  20.     {
  21.         for (int i = 0; i <= 3 * r * (r + 1); i++)
  22.         {
  23.             vector<int> vt(7, i);
  24.             while (1)
  25.             {
  26.                 int e = 1;
  27.                 REP(j, 6)
  28.                 {
  29.                     vt[j] = adj[vt[j]][j];
  30.                     if (vt[j] == -1 || vt[j] > 3 * (r) * (r + 1))
  31.                     {
  32.                         e = -1;
  33.                         break;
  34.                     }
  35.                     if (dd[vt[j]])
  36.                         e = 0;
  37.                 }
  38.                 if (e == -1)
  39.                     break;
  40.                 else
  41.                 {
  42.                     if (e == 1)
  43.                         ans++;
  44.                     int se = vt[2];
  45.                     vector<int> vt2 = vt;
  46.                     while (1)
  47.                     {
  48.                         int e = 1;
  49.                         REP(j, 6)
  50.                         {
  51.                             int angle = (j + 2) % 6;
  52.                             if (angle == 0)
  53.                                 angle = 6;
  54.                             vt2[j] = adj[vt2[j]][angle];
  55.                             if (j == 1 && vt2[j] == se)
  56.                             {
  57.                                 e = -1;
  58.                                 break;
  59.                             }
  60.                             if (vt2[j] == -1 || vt2[j] > 3 * (r) * (r + 1))
  61.                             {
  62.                                 e = -1;
  63.                                 break;
  64.                             }
  65.                             if (dd[vt2[j]])
  66.                                 e = 0;
  67.                         }
  68.                         if (e == -1)
  69.                             break;
  70.                         else if (e == 1)
  71.                             ans++;
  72.                     }
  73.                 }
  74.             }
  75.         }
  76.         cout << ans << '\n';
  77.     }
  78. }
  79. namespace sub6
  80. {
  81.     int adj2[(int)3e5 + 5][12][7], huong[305][7];
  82.     vector<int> popbit[1005];
  83.     inline int get(int x, int k, int d)
  84.     {
  85.         // cerr << x << ' ' << k << ' ' << d << '\n';
  86.         if (x == -1)
  87.             return x;
  88.         for (auto i : popbit[k])
  89.         {
  90.             if (x == -1)
  91.                 return x;
  92.             x = adj2[x][i][d];
  93.         }
  94.         return x;
  95.     }
  96.     void solve()
  97.     {
  98.         REP(i, r)
  99.         {
  100.             ans += i;
  101.         }
  102.         ans *= ans;
  103.         // cbi truoc mang adj2
  104.         memset(adj2, -1, sizeof adj2);
  105.         for (int i = 0; i <= 3 * r * (r + 1); i++)
  106.         {
  107.             REP(j, 6)
  108.             adj2[i][0][j] = adj[i][j];
  109.         }
  110.         for (int k = 1; (1 << k) <= 1000; k++)
  111.         {
  112.             REP(j, 6)
  113.             {
  114.                 for (int i = 0; i <= 3 * r * (r + 1); i++)
  115.                 {
  116.                     if (adj2[i][k - 1][j] == -1)
  117.                     {
  118.                         adj2[i][k][j] = -1;
  119.                         continue;
  120.                     }
  121.                     adj2[i][k][j] = adj2[adj2[i][k - 1][j]][k - 1][j];
  122.                 }
  123.             }
  124.         }
  125.         REP(i, 1000)
  126.         {
  127.             for (int j = 0; (1 << j) <= i; j++)
  128.             {
  129.                 if (i >> j & 1)
  130.                     popbit[i].pb(j);
  131.             }
  132.         }
  133.         // solve
  134.         vector<int> vt(7);
  135.         for (int i : bo)
  136.         {
  137.             FOR(h, 0, r)
  138.             {
  139.                 REP(d, 6)
  140.                 {
  141.                     huong[h][d] = get(i, h, d);
  142.                 }
  143.             }
  144.             REP(m, r)
  145.             {
  146.                 REP0(h, m)
  147.                 {
  148.                     // A
  149.                     int start = huong[h][6];
  150.                     int tam = get(start, m, 4);
  151.                     int e = 1;
  152.                     REP(j, 6)
  153.                     {
  154.                         vt[j] = get(tam, m, j);
  155.                         int angle = (j + 2) % 6;
  156.                         if (angle == 0)
  157.                             angle = 6;
  158.                         vt[j] = get(vt[j], h, angle);
  159.                         if (vt[j] == -1 || vt[j] > 3 * (r) * (r + 1))
  160.                         {
  161.                             e = -1;
  162.                             break;
  163.                         }
  164.                     }
  165.                     if (e == 1 && vt[1] == i)
  166.                         ans--;
  167.                     // B
  168.                     start = huong[h][1];
  169.                     tam = get(start, m, 5);
  170.                     e = 1;
  171.                     REP(j, 6)
  172.                     {
  173.                         vt[j] = get(tam, m, j);
  174.                         int angle = (j + 2) % 6;
  175.                         if (angle == 0)
  176.                             angle = 6;
  177.                         vt[j] = get(vt[j], h, angle);
  178.                         if (vt[j] == -1 || vt[j] > 3 * (r) * (r + 1))
  179.                         {
  180.                             e = -1;
  181.                             break;
  182.                         }
  183.                     }
  184.                     if (e == 1 && !dd[vt[1]] && vt[2] == i)
  185.                         ans--;
  186.                     // C
  187.                     start = huong[h][2];
  188.                     tam = get(start, m, 6);
  189.                     e = 1;
  190.                     REP(j, 6)
  191.                     {
  192.                         vt[j] = get(tam, m, j);
  193.                         int angle = (j + 2) % 6;
  194.                         if (angle == 0)
  195.                             angle = 6;
  196.                         vt[j] = get(vt[j], h, angle);
  197.                         if (vt[j] == -1 || vt[j] > 3 * (r) * (r + 1))
  198.                         {
  199.                             e = -1;
  200.                             break;
  201.                         }
  202.                     }
  203.                     if (e == 1 && !dd[vt[1]] && !dd[vt[2]] && vt[3] == i)
  204.                         ans--;
  205.                     // D
  206.                     start = huong[h][3];
  207.                     tam = get(start, m, 1);
  208.                     e = 1;
  209.                     REP(j, 6)
  210.                     {
  211.                         vt[j] = get(tam, m, j);
  212.                         int angle = (j + 2) % 6;
  213.                         if (angle == 0)
  214.                             angle = 6;
  215.                         vt[j] = get(vt[j], h, angle);
  216.                         if (vt[j] == -1 || vt[j] > 3 * (r) * (r + 1))
  217.                         {
  218.                             e = -1;
  219.                             break;
  220.                         }
  221.                     }
  222.                     if (e == 1 && !dd[vt[1]] && !dd[vt[2]] && !dd[vt[3]] && vt[4] == i)
  223.                         ans--;
  224.                     // E
  225.                     start = huong[h][4];
  226.                     tam = get(start, m, 2);
  227.                     e = 1;
  228.                     REP(j, 6)
  229.                     {
  230.                         vt[j] = get(tam, m, j);
  231.                         int angle = (j + 2) % 6;
  232.                         if (angle == 0)
  233.                             angle = 6;
  234.                         vt[j] = get(vt[j], h, angle);
  235.                         if (vt[j] == -1 || vt[j] > 3 * (r) * (r + 1))
  236.                         {
  237.                             e = -1;
  238.                             break;
  239.                         }
  240.                     }
  241.                     if (e == 1 && !dd[vt[1]] && !dd[vt[2]] && !dd[vt[3]] && !dd[vt[4]] && vt[5] == i)
  242.                         ans--;
  243.                     // F
  244.                     start = huong[h][5];
  245.                     tam = get(start, m, 3);
  246.                     e = 1;
  247.                     REP(j, 6)
  248.                     {
  249.                         vt[j] = get(tam, m, j);
  250.                         int angle = (j + 2) % 6;
  251.                         if (angle == 0)
  252.                             angle = 6;
  253.                         vt[j] = get(vt[j], h, angle);
  254.                         if (vt[j] == -1 || vt[j] > 3 * (r) * (r + 1))
  255.                         {
  256.                             e = -1;
  257.                             break;
  258.                         }
  259.                     }
  260.                     if (e == 1 && !dd[vt[1]] && !dd[vt[2]] && !dd[vt[3]] && !dd[vt[4]] && !dd[vt[5]] && vt[6] == i)
  261.                         ans--;
  262.                 }
  263.             }
  264.         }
  265.         cout << ans << '\n';
  266.     }
  267. }
  268. int32_t main()
  269. {
  270. #define task ""
  271.     if (fopen(task ".inp", "r"))
  272.     {
  273.         freopen(task ".inp", "r", stdin);
  274.         freopen(task ".out", "w", stdout);
  275.     }
  276.     cin.tie(0)->sync_with_stdio(0);
  277.     cin >> r >> n;
  278.     if (n == 0)
  279.     {
  280.         int ans = 0;
  281.         REP(i, r)
  282.         {
  283.             ans += i;
  284.         }
  285.         cout << ans * ans << '\n';
  286.         return 0;
  287.     }
  288.     opp[1] = 4;
  289.     opp[2] = 5;
  290.     opp[3] = 6;
  291.     opp[4] = 1;
  292.     opp[5] = 2;
  293.     opp[6] = 3;
  294.     memset(adj, -1, sizeof adj);
  295.     REP(i, n)
  296.     {
  297.         int x;
  298.         cin >> x;
  299.         dd[x] = 1;
  300.         bo.pb(x);
  301.     }
  302.     REP(i, 6)
  303.     {
  304.         adj[0][i] = i;
  305.         adj[i][opp[i]] = 0;
  306.     }
  307.     int s = 2;
  308.     REP(i, 6)
  309.     {
  310.         int numitr = (i + 1) % 6;
  311.         if (numitr == 0)
  312.             numitr = 6;
  313.         s = (s + 1) % 6;
  314.         if (s == 0)
  315.             s = 6;
  316.         adj[i][s] = numitr;
  317.         adj[numitr][opp[s]] = i;
  318.     }
  319.     REP(i, r)
  320.     {
  321.         int x = 3 * (i + 2) * (i + 1), angle = 6, same = 2;
  322.         for (int itr = 3 * i * (i - 1) + 1, cnt = 0; itr <= 3 * (i + 1) * i; itr++, cnt = (cnt + 1) % i)
  323.         {
  324.             int num = (cnt == 0) ? 3 : 2;
  325.             if (cnt == 0)
  326.             {
  327.                 same = (same + 1) % 6;
  328.                 if (same == 0)
  329.                     same = 6;
  330.             }
  331.             int numadj = itr + 1;
  332.             if (numadj == 3 * (i + 1) * i + 1)
  333.                 numadj = 3 * i * (i - 1) + 1;
  334.             adj[itr][same] = numadj;
  335.             adj[numadj][opp[same]] = itr;
  336.             int x2 = x, angle2 = angle;
  337.             REP(j, num)
  338.             {
  339.                 adj[itr][angle2] = x2;
  340.                 adj[x2][opp[angle2]] = itr;
  341.                 angle2 = (angle2 + 1) % 6;
  342.                 if (angle2 == 0)
  343.                     angle2 = 6;
  344.                 x2++;
  345.                 if (x2 == 3 * (i + 2) * (i + 1) + 1)
  346.                     x2 = 3 * (i + 1) * i + 1;
  347.             }
  348.             REP(j, num - 1)
  349.             {
  350.                 x++;
  351.                 if (x == 3 * (i + 2) * (i + 1) + 1)
  352.                     x = 3 * (i + 1) * i + 1;
  353.             }
  354.             REP(j, num - 2)
  355.             {
  356.                 angle = (angle + 1) % 6;
  357.                 if (angle == 0)
  358.                     angle = 6;
  359.             }
  360.         }
  361.     }
  362.     if (r <= 100)
  363.     {
  364.         sub125::solve();
  365.         return 0;
  366.     }
  367.     sub6::solve();
  368.     // printclock;
  369.     return 0;
  370. }
Success #stdin #stdout 0.01s 5768KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0
https://ideone.com/kIRET7
language:
C++14 (gcc 8.3)
created:
111 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!