Advertisement
Guest User

Untitled

a guest
Dec 13th, 2019
112
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 4.09 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. #define pii pair<int, int>
  3. #define fi first
  4. #define se second
  5. #define maxc 1000500
  6. #define watch(x) cout << (#x) << " is " << (x) << endl;
  7. using namespace std;
  8. int C[1000500];
  9.  
  10.  
  11. int main() {
  12.     int N, K;
  13.     cin >> N >> K;
  14.  
  15.     unordered_map<int, int> ind;
  16.     unordered_map<int, unordered_map<int, char>> thing;
  17.     unordered_map<int, unordered_map<int, int>> turn;
  18.  
  19.     string player = "ashley";
  20.  
  21.     vector<pii> filled;
  22.     // column -> row
  23.     for(int i = 1; i <= N; i++) {
  24.         int cute;
  25.         cin >> cute;
  26.  
  27.         ind[cute]++;
  28.  
  29.         int r = ind[cute];
  30.         int c = cute;
  31.         if(player == "ashley") {
  32.             thing[r][c] = 'a';
  33.             turn[r][c] = i;
  34.             player = "oleg";
  35.         } else {
  36.             thing[r][c] = 'o';
  37.             turn[r][c] = i;
  38.             player = "ashley";
  39.         }
  40.  
  41.         // cout << "emplacing to " << r << " " << c<<endl;
  42.  
  43.         filled.emplace_back(r,c);
  44.     }
  45.  
  46.     int earliest = INT_MAX;
  47.     char won = '?';
  48.     for(pii x: filled) {
  49.         int r = x.fi;
  50.         int c = x.se;
  51.         char pl = thing[r][c];
  52.  
  53.         // cout << "currently on " << r << " " << c << endl;
  54.  
  55.         // right
  56.         int rlen = 1;
  57.         int rma = turn[r][c];
  58.  
  59.         for(int i = 1; i <= K-1; i++) {
  60.             // check if exists
  61.             if(c+1 <= maxc) {
  62.                 if(ind[c+i] >= r) {
  63.                     if(thing[r][c+i] == pl) {
  64.                         // cout << "thing of " << r << " " << c+i << " is " << thing[r][c+i] << endl;
  65.                         rlen++;
  66.                         rma = max(rma, turn[r][c+i]);
  67.                     } else {
  68.                         break;
  69.                     }
  70.                 } else {
  71.                     break;
  72.                 }
  73.             }
  74.  
  75.  
  76.             if(rlen >= K) break;
  77.         }
  78.  
  79.  
  80.         // down
  81.         int dlen = 1;
  82.         int dma = turn[r][c];
  83.        
  84.         for(int i = 1; i <= K-1; i++) {
  85.             // check if exists
  86.             if(r-i >= 1) {
  87.                 if(thing[r-i][c] == pl) {
  88.                     dlen++;
  89.                     dma = max(dma, turn[r-i][c]);
  90.                 } else break;
  91.             }
  92.  
  93.             if(dlen >= K) break;
  94.  
  95.         }
  96.  
  97.  
  98.         // down right
  99.         int drlen = 1;
  100.         int drma = turn[r][c];
  101.         for(int i = 1; i <= K-1; i++) {
  102.             if(c-i >= 1)
  103.             if(ind[c-i] >= r+i) {
  104.                 if(thing[r+i][c-i] == pl) {
  105.                     drlen++;
  106.                     drma = max(drma, turn[r+i][c-i]);
  107.                 }
  108.             }
  109.  
  110.             if(drlen >= K) break;
  111.  
  112.         }
  113.  
  114.         // up right
  115.         int urlen = 1;
  116.         int urma = turn[r][c];
  117.         for(int i = 1; i <= K-1; i++) {
  118.             if(c+i <= maxc)
  119.             if(ind[c+i] >= r+i) {
  120.                 if(thing[r+i][c+i] == pl) {
  121.                     urlen++;
  122.                     urma = max(urlen, turn[r+i][c+i]);
  123.                 }
  124.             }
  125.             if(urlen >= K) break;
  126.  
  127.         }
  128.  
  129.         // watch(rlen)
  130.         // watch(dlen)
  131.         // watch(drlen)
  132.         // watch(urlen)
  133.         if(rlen >= K) {
  134.             if(rma < earliest) {
  135.                 earliest = rma;
  136.                 won = pl;
  137.  
  138.             }
  139.            
  140.         }
  141.  
  142.         if(dlen >= K) {
  143.              if(dma < earliest) {
  144.                 earliest = dma;
  145.                 won = pl;
  146.  
  147.             }
  148.         }
  149.  
  150.         if(drlen >= K) {
  151.              if(drma < earliest) {
  152.                 earliest = drma;
  153.                 won = pl;
  154.  
  155.             }
  156.         }
  157.  
  158.         if(urlen >= K) {
  159.             if(urma < earliest) {
  160.                 earliest = urma;
  161.                 won = pl;
  162.  
  163.             }
  164.         }
  165.  
  166.         // cout << endl;
  167.     }
  168.  
  169.     if(won == 'a') cout << "Asheley ";
  170.     else cout << "Oleg ";
  171.     cout << earliest << endl;
  172.  
  173.    
  174.  
  175.  
  176.  
  177.     // for(int i = 1; i < 1000500; i++) {
  178.     //     if(grid[i].size()) {
  179.     //         for(char x: grid[i]) {
  180.     //             cout << x << " ";
  181.     //         }
  182.     //         cout << endl;
  183.     //     }
  184.     // }
  185.  
  186.  
  187.  
  188. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement