提出 #70830158

---

ソースコード 拡げる

/* GLORY TO HANUMAN */
#include <bits/stdc++.h>
using namespace std;

#define int long long
#ifndef ONLINE_JUDGE
#include "debug.h"
#define deb(x...) cerr << "[" << #x << "] = ["; _print(x)
#else
#define deb(x...)
#endif

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

template<class T>
void output (vector<T> &a) {for (auto &x : a) {cout << x << ' ';}cout << '\n';}


/*        

     if string is not a valid bracket sequence First wins
     
     if string i a valid bracket sequence :
          if k is odd :
               First wins..
          if k is even :

               first guy in his turn will always be able to make the
               sequence invalid. 

*/

const int INF = 1E9;

bool solve() {
     string s;
     cin >> s;
     int k;
     cin >> k;
     const int n = (int) s.size();
     {
          int bal = 0;
          for (int i = 0; i < n; ++i) {
               bal += s[i] == '(' ? +1 : -1;
               if (bal < 0) {
                    return true;
               }
          }
          if (bal != 0 || k % 2) {
               return true;
          }
     }
     vector<int> prv(n, -1);
     {
          stack<int> stk;
          for (int i = 0; i < n; ++i) {
               if (s[i] == '(') {
                    stk.push(i);
               }
               else {
                    assert(!stk.empty());
                    prv[i] = stk.top();
                    stk.pop();
               }
          }
     }
     vector<int> nxt(n, -1);
     {
          stack<int> stk;
          for (int i = n - 1; i >= 0; --i) {
               if (s[i] == ')') {
                    stk.push(i);
               }
               else {
                    assert(!stk.empty());
                    nxt[i] = stk.top();
                    stk.pop();
               }
          }
     }
     {
          int i = 0, j = n - 1;
          while (j - i > k) {
               if (nxt[i] == i + 1) {
                    i = nxt[i] + 1;
               }
               else if (nxt[i] == j) {
                    i++, j--;
               }
               else {
                    return true;
               }
          }
     }
     {
          int i = 0, j = n - 1;
          while (j - i > k) {
               if (prv[j] == j - 1) {
                    j = prv[j] - 1;
               }
               else if (prv[j] == i) {
                    i++, j--;
               }
               else {
                    return true;
               }
          }
     }
     return false;
}    


int32_t main() {
     ios::sync_with_stdio(false);
     cin.tie(nullptr);

     #ifndef ONLINE_JUDGE
          freopen("input.txt", "r", stdin);
          freopen("output.txt", "w", stdout);
          freopen("error.txt", "w", stderr);
     #endif

     int t = 1;
     cin >> t;
     
     for (int cases = 1; cases <= t; ++cases) {
          cout << (solve() ? "First" : "Second") << "\n";
     }

     #ifndef ONLINE_JUDGE
          double T = 1000.0 * clock() / CLOCKS_PER_SEC;
          cout << "\n[Finished in " << T << "ms]";
          cerr << "\n[Finished in " << T << "ms]";
     #endif

     return 0;
}

提出情報

ジャッジ結果