結果
| 問題 |
No.2924 <===Super Spaceship String===>
|
| コンテスト | |
| ユーザー |
 Reid
|
| 提出日時 | 2024-10-19 17:04:06 |
| 言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
AC
|
| 実行時間 | 19 ms / 2,000 ms |
| コード長 | 6,686 bytes |
| コンパイル時間 | 6,106 ms |
| コンパイル使用メモリ | 275,732 KB |
| 実行使用メモリ | 7,784 KB |
| 最終ジャッジ日時 | 2024-10-19 17:04:14 |
| 合計ジャッジ時間 | 6,873 ms |
|
ジャッジサーバーID （参考情報） |
judge2 / judge3 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 2 |
| other | AC * 12 |
コンパイルメッセージ
main.cpp:112: warning: "debug" redefined
112 | #define debug(var)
|
main.cpp:43: note: this is the location of the previous definition
43 | #define debug(var) DEBUG(#var, var)
|
ソースコード
#include <bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
#include<ext/pb_ds/tag_and_trait.hpp>
using namespace std;
using namespace __gnu_pbds;
#define rep(i,n) for(int i = 0;i<(n);i++)
#define per(i,n) for(int i = (n-1);i>=0;i--)
#define nfor(i,b,e) for(int i = b;i<(e);i++)
#define Sort(a) sort((a).begin(), (a).end())
#define Rev(a) reverse((a).begin(), (a).end())
#define all(...) std::begin(__VA_ARGS__), std::end(__VA_ARGS__)
#define rall(...) std::rbegin(__VA_ARGS__), std::rend(__VA_ARGS__)//reverseしてからall
#define endl '\n'
#define YesNo(bool) if(bool){cout<<"Yes"<<endl;}else{cout<<"No"<<endl;}
#include <limits>
// Tu は最大値のある符号無し整数型 (型チェックに必要な static_assert などは省略)
template <typename Tu>
static inline constexpr bool is_multiplication_safe(Tu a, Tu b){
return !a || b <= std::numeric_limits<Tu>::max() / a;
}
template <typename Tu>
static inline constexpr bool is_addition_safe(Tu a, Tu b){
if(a*b <= 0) return true;
else if(a<0 && b<0) return b >= std::numeric_limits<Tu>::max() - a;
else if(a>0 && b>0) return b <= std::numeric_limits<Tu>::max() - a;
}
//O(NlogN)の計算量が必要
template <typename T>
double median(std::vector<T> numbers) {
std::sort(numbers.begin(), numbers.end());
size_t size = numbers.size();
if (size % 2 == 0) return (numbers[size / 2 - 1] + numbers[size / 2]) / 2.0;
else return numbers[size / 2];
}
#define debug(var) DEBUG(#var, var)
#ifdef _DEBUG
// 基本データ型用のデバッグ関数
template<typename T>
void DEBUG(const char* varName, const T& value) {
std::cout << varName << ":" << value << endl;
}
// std::string用のデバッグ関数
void DEBUG(const char* varName, const std::string& value) {
std::cout << varName << ":"<< value << endl;
}
// std::array用のデバッグ関数
template<typename T, std::size_t N>
void DEBUG(const char* varName, const std::array<T, N>& arr) {
std::cout << varName << ":";
for (const auto& el : arr) {
std::cout << el << " ";
}
std::cout << endl;
}
// std::vector用のデバッグ関数
template<typename T>
void DEBUG(const char* varName, const std::vector<T>& vec) {
std::cout << varName << ":";
for (const auto& el : vec) {
std::cout << el << " ";
}
std::cout << endl;
}
// std::stack用のデバッグ関数
template<typename T>
void DEBUG(const char* varName, const std::stack<T> stk) {
std::cout << varName << ":";
std::stack<T> copy = stk; // コピーして内容を出力
std::vector<T> res;
while (!copy.empty()) {
res.push_back(copy.top());
copy.pop();
}
Rev(res);
debug(res);
}
// std::set用のデバッグ関数
template<typename T>
void DEBUG(const char* varName, const std::set<T>& s) {
std::cout << varName << ":";
for (const auto& el : s) {
std::cout << el << " ";
}
std::cout << endl;
}
// 二次元配列用のデバッグ関数
template<typename T>
void DEBUG(const char* varName, const std::vector<std::vector<T>>& matrix) {
std::cout << varName << ":"<< endl;
for (const auto& row : matrix) {
for (const auto& el : row) {
std::cout << el << " ";
}
std::cout << endl;
}
}
#else
#define debug(var)
#endif
//<int>を<使いたい型>に書き変える
//*orderd_set.find_by_order(i)で値を取得する。
using ordered_set = tree<char, null_type, less<char>, rb_tree_tag, tree_order_statistics_node_update>;
using ll = long long;
using ull = unsigned long long;
using Lf = long double;
using vi = vector<int>;
using vc = vector<char>;
using vvi = vector<vector<int>>;
using vvc = vector<vector<char>>;
using vvvi = vector<vector<vector<int>>>;
using vll = vector<ll>;
using vvll = vector<vector<ll>>;
using Pii = pair<int,int>;
#define make(x,y) make_pair(x,y)
//vector to string
string to_string(vector<int> a){
int n = a.size();
string res = "";
rep(i,n) res += char(a[i]+'0');
return res;
}
long double euclid_dist(long double xi,long double yi,long double xj,long double yj){
return sqrt((xi-xj)*(xi-xj)+(yi-yj)*(yi-yj));
}
ull factorial(int n){
if(n==0||n==1) return 1ULL;
else return factorial(n-1)*n;
}
template<int MOD>
struct ModInt {
static const int Mod = MOD;
unsigned x;
ModInt() : x(0) { }
ModInt(signed sig) { int sigt = sig % MOD; if (sigt < 0) sigt += MOD; x = sigt; }
ModInt(signed long long sig) { int sigt = sig % MOD; if (sigt < 0) sigt += MOD; x = sigt; }
int get() const { return (int)x; }
ModInt &operator+=(ModInt that) { if ((x += that.x) >= MOD) x -= MOD; return *this; }
ModInt &operator-=(ModInt that) { if ((x += MOD - that.x) >= MOD) x -= MOD; return *this; }
ModInt &operator*=(ModInt that) { x = (unsigned long long)x * that.x % MOD; return *this; }
ModInt operator+(ModInt that) const { return ModInt(*this) += that; }
ModInt operator-(ModInt that) const { return ModInt(*this) -= that; }
ModInt operator*(ModInt that) const { return ModInt(*this) *= that; }
};
using mint = ModInt<1000000007>;
int main(){
ios::sync_with_stdio(false);
cin.tie(nullptr);
string s; cin >> s;
stack<pair<char,int>> stk;
int n = s.size();
stk.push(make_pair(s[n-1],1));
for(int i = n-2;i>=0;i--){
if(s[i] == '=' && stk.top().first==s[i]){
stk.top().second++;
}else{
stk.push(make_pair(s[i],1));
}
}
stack<pair<char,int>> stk2;
while(!stk.empty()){
char c = stk.top().first;
int num = stk.top().second;
stk.pop();
if(!stk2.empty() && stk2.top().first==c && c=='='){
stk2.top().second += num;
continue;
}
if(stk2.size()>=2 && c == '>'){
auto pop1 = stk2.top();
if(pop1.first=='=') stk2.pop();
else{
stk2.push(make_pair(c,num));
continue;
}
auto pop2 = stk2.top();
if(pop2.first=='<') stk2.pop();//ここが1だった・・・
else{
stk2.push(pop1);
stk2.push(make_pair(c,num));
continue;
}
}else{
stk2.push(make_pair(c,num));
}
}
ll ans = 0;
vector<char> dbg;
while(!stk2.empty()){
dbg.push_back(stk2.top().first);
ans += stk2.top().second;
stk2.pop();
}
Rev(dbg);
debug(dbg);
cout <<ans << endl;
return 0;
}
//パスグラフとは？？？？？
//もっとアルゴリズム使え！！！！！
// <========<>======>