oj.uz

Submission #798127

# Submission time Handle Problem Language Result Execution time Memory
798127 2023-07-30T11:37:59 Z Sam_a17 parentrises (BOI18_parentrises) C++17
56 / 100
 23 ms 3440 KB 
#define _CRT_SECURE_NO_WARNINGS
#include <bits/stdc++.h>
// #include <atcoder/all>
#include <cstdio>
using namespace std;
 
#ifndef ONLINE_JUDGE
#define dbg(x) cerr << #x <<" "; print(x); cerr << endl;
#else
#define dbg(x)
#endif
 
#define sz(x) (int((x).size()))
#define len(x) (int)x.length()
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define clr(x) (x).clear()
#define blt(x) __builtin_popcount(x)
#define uniq(x) x.resize(unique(all(x)) - x.begin());
 
// #define pb push_back
#define popf pop_front
#define popb pop_back
#define ld long double
#define ll long long
 
void print(long long t) {cerr << t;}
void print(int t) {cerr << t;}
void print(string t) {cerr << t;}
void print(char t) {cerr << t;}
void print(double t) {cerr << t;}
void print(unsigned long long t) {cerr << t;}
void print(long double t) {cerr << t;}
 
template <class T, class V> void print(pair <T, V> p);
template <class T> void print(vector <T> v);
template <class T> void print(set <T> v);
template <class T, class V> void print(map <T, V> v);
template <class T> void print(multiset <T> v);
template <class T> void print(T v[],T n) {cerr << "["; for(int i = 0; i < n; i++) {cerr << v[i] << " ";} cerr << "]";}
template <class T, class V> void print(pair <T, V> p) {cerr << "{"; print(p.first); cerr << ","; print(p.second); cerr << "}";}
template <class T> void print(vector <T> v) {cerr << "[ "; for (T i : v) {print(i); cerr << " ";} cerr << "]";}
template <class T> void print(deque <T> v) {cerr << "[ "; for (T i : v) {print(i); cerr << " ";} cerr << "]";}
template <class T> void print(set <T> v) {cerr << "[ "; for (T i : v) {print(i); cerr << " ";} cerr << "]";}
template <class T> void print(multiset <T> v) {cerr << "[ "; for (T i : v) {print(i); cerr << " ";} cerr << "]";}
template <class T, class V> void print(map <T, V> v) {cerr << "[ "; for (auto i : v) {print(i); cerr << " ";} cerr << "]";}
 
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
#define nl '\n'
 
// for random generations
mt19937 myrand(chrono::steady_clock::now().time_since_epoch().count());
// mt19937 myrand(131);
 
// for grid problems
int dx[8] = {1,0,-1,0,1,-1,1,-1};
int dy[8] = {0,1,0,-1,1,1,-1,-1};
char ch[4] = {'v', '>', '^', '<'};
 
long long ka() {
    long long x = 0;
    bool z = false;
    while (1)
    {
        char y = getchar();
        if (y == '-')
            z = true;
        else if ('0' <= y && y <= '9')
            x = x * 10 + y - '0';
        else
        {
            if (z)
                x *= -1;
            return x;
        }
    }
}
 
// lowest / (1 << 17) >= 1e5 / (1 << 18) >= 2e5 / (1 << 21) >= 1e6
void fastIO() {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr); cout.tie(nullptr);
}
// file in/out
void setIO(string str = "") {
  fastIO();
 
  if (str != "") {
    freopen((str + ".in").c_str(), "r", stdin);
    freopen((str + ".out").c_str(), "w", stdout);
  } else if(str == "input") {
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
  }
}
 
// Indexed Set
template <class T> using Tree = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

const long long mod = 1e9 + 7;
const int N = 105;
long long dp[N][2 * N + 2][2 * N + 2];

long long add(long long a, long long b) {
  return (a + b) % mod;
}

long long mult(long long a, long long b) {
  return (a * b) % mod;
}

long long sub(long long a, long long b) {
  return (a - b + 2 * mod) % mod;
}

bool check(string s) {
  int n = sz(s);
  string ans(n, '.');
  int a = 0, b = 0;
  int ok = 1;
  for(int i = 0; i < n; i++) {
    if(s[i] == '(') {
      a++, b++;
      ans[i] = 'G';
    } else {
      if(a > b) {
        a--;
        ans[i] = 'R';
      } else {
        b--;
        ans[i] = 'B';
      }
    }

    if(a < 0 || b < 0) {
      ok = 0;
      break;
    }
  }

  int mn_a = a, mn_b = b;
  if(mn_a || mn_b) {
    for(int i = n - 1; i >= 0; i--) {
      int wh = 0;
      if(ans[i] == 'G') {
        if(mn_a > mn_b) {
          ans[i] = 'B';
          mn_a--;
        } else {
          mn_b--;
          ans[i] = 'R';
        }
      } else {
        if(ans[i] == 'R' && mn_b) {
          mn_b--;
          ans[i] = 'G';
        } else if(ans[i] == 'B' && mn_a) {
          mn_a--;
          ans[i] = 'G';
        }
      }

      if(mn_a == 0 && mn_b == 0) {
        break;
      }
    }

    a = 0, b = 0;
    for(int i = 0; i < n; i++) {
      if(ans[i] == 'G') {
        if(s[i] == '(') {
          a++, b++;
        } else {
          a--, b--;
        }
      } else if(ans[i] == 'R') {
        if(s[i] == '(') {
          a++; 
        } else {
          a--;
        }
      } else {
        if(s[i] == '(') {
          b++; 
        } else {
          b--;
        }
      }

      if(a < 0 || b < 0) {
        ok = 0;
      }
    }

    if(a != 0 || b != 0) {
      ok = 0;
    }
  }

  if(!ok) {
    return false;
  } else {
    return true;
  }
}

vector<long long> pte = {0,1,2,2,6,12,18,43,86,148,326,652,1194,2531,5062};

void solve_() {
  int t; cin >> t;

  if(t == 1) {
    int q; cin >> q;
    while(q--) {
      string s; cin >> s;
      int n = sz(s);
      int a = 0, b = 0;

      string ans(n, '.');
      int ok = 1;
      for(int i = 0; i < n; i++) {
        if(s[i] == '(') {
          a++, b++;
          ans[i] = 'G';
        } else {
          if(a > b) {
            a--;
            ans[i] = 'R';
          } else {
            b--;
            ans[i] = 'B';
          }
        }

        if(a < 0 || b < 0) {
          ok = 0;
          break;
        }
      }

      int mn_a = a, mn_b = b;
      if(mn_a || mn_b) {
        for(int i = n - 1; i >= 0; i--) {
          int wh = 0;
          if(ans[i] == 'G') {
            if(mn_a > mn_b) {
              ans[i] = 'B';
              mn_a--;
            } else {
              mn_b--;
              ans[i] = 'R';
            }
          } else {
            if(ans[i] == 'R' && mn_b) {
              mn_b--;
              ans[i] = 'G';
            } else if(ans[i] == 'B' && mn_a) {
              mn_a--;
              ans[i] = 'G';
            }
          }

          if(mn_a == 0 && mn_b == 0) {
            break;
          }
        }

        a = 0, b = 0;
        for(int i = 0; i < n; i++) {
          if(ans[i] == 'G') {
            if(s[i] == '(') {
              a++, b++;
            } else {
              a--, b--;
            }
          } else if(ans[i] == 'R') {
            if(s[i] == '(') {
              a++; 
            } else {
              a--;
            }
          } else {
            if(s[i] == '(') {
              b++; 
            } else {
              b--;
            }
          }

          if(a < 0 || b < 0) {
            ok = 0;
          }
        }

        if(a != 0 || b != 0) {
          ok = 0;
        }
      }

      if(!ok) {
        cout << "impossible" << '\n';
      } else {
        cout << ans << '\n';
      }
    }
  } else {
    int q; cin >> q;
    while(q--){
      int n; cin >> n;
      cout << pte[n - 1] << '\n';
    }
  }
}
 
int main() {
  setIO();

  // vector<long long> dp(32);
  // for(int i = 1; i <= 15; i++) {
  //   dbg(i)
  //   for(int mask = 0; mask < (1 << i); mask++) {
  //     string si = "";
  //     for(int j = 0; j < i; j++) {
  //       if(mask & (1 << j)) {
  //         si += ")";
  //       } else {
  //         si += "(";
  //       }
  //     }
  //     dp[i] += check(si);
  //   }
  // }

  // cout << "{";
  // for(int i = 1; i <= 15; i++) {
  //   cout << dp[i] << ",";
  // }
  // cout << "}";
  // cout << endl;
  // exit(0);
 
  auto solve = [&](int test_case)-> void {
    while(test_case--) {
      solve_();
    }
  };
 
  int test_cases = 1; 
  // cin >> test_cases;
  solve(test_cases);
 
  return 0;
}

Compilation message

parentrises.cpp: In function 'bool check(std::string)':
parentrises.cpp:145:11: warning: unused variable 'wh' [-Wunused-variable]
  145 |       int wh = 0;
      |           ^~
parentrises.cpp: In function 'void solve_()':
parentrises.cpp:245:15: warning: unused variable 'wh' [-Wunused-variable]
  245 |           int wh = 0;
      |               ^~
parentrises.cpp: In function 'void setIO(std::string)':
parentrises.cpp:90:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   90 |     freopen((str + ".in").c_str(), "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
parentrises.cpp:91:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   91 |     freopen((str + ".out").c_str(), "w", stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
parentrises.cpp:93:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   93 |     freopen("input.txt", "r", stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
parentrises.cpp:94:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   94 |     freopen("output.txt", "w", stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct

Subtask #2
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 1 ms 212 KB Output is correct

Subtask #4
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 0 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Correct 0 ms 340 KB Output is correct
14 Correct 0 ms 340 KB Output is correct
15 Correct 1 ms 340 KB Output is correct
16 Correct 2 ms 340 KB Output is correct
17 Correct 2 ms 596 KB Output is correct
18 Correct 1 ms 340 KB Output is correct
19 Correct 2 ms 468 KB Output is correct
20 Correct 2 ms 596 KB Output is correct
21 Correct 23 ms 1036 KB Output is correct
22 Correct 16 ms 3300 KB Output is correct
23 Correct 8 ms 1320 KB Output is correct
24 Correct 14 ms 1860 KB Output is correct
25 Correct 16 ms 3440 KB Output is correct

Subtask #5
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct

Subtask #6
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Incorrect 0 ms 340 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #7
0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Incorrect 0 ms 340 KB Output isn't correct
3 Halted 0 ms 0 KB -