提出 #15869137 - AtCoder Beginner Contest 175

コンテスト時間: 2020-08-15 21:00:00+0900 ~ 2020-08-15 22:40:00+0900 (100分) AtCoderホームへ戻る

提出 #15869137

ソースコード拡げる

#include <bits/stdc++.h>
using namespace std;

using ll = long long;
using pii = pair<int, int>;
template <class T>
using V = vector<T>;
template <class T>
using VV = V<V<T>>;

#define pb push_back
#define eb emplace_back
#define mp make_pair
#define fi first
#define se second
#define rep(i, n) rep2(i, 0, n)
#define rep2(i, m, n) for (int i = m; i < (n); i++)
#define per(i, b) per2(i, 0, b)
#define per2(i, a, b) for (int i = int(b) - 1; i >= int(a); i--)
#define ALL(c) (c).begin(), (c).end()
#define SZ(x) ((int)(x).size())

constexpr ll TEN(int n) { return (n == 0) ? 1 : 10 * TEN(n - 1); }

template <class T, class U>
void chmin(T& t, const U& u) {
    if (t > u) t = u;
}
template <class T, class U>
void chmax(T& t, const U& u) {
    if (t < u) t = u;
}

template <class T, class U>
ostream& operator<<(ostream& os, const pair<T, U>& p) {
    os << "(" << p.first << "," << p.second << ")";
    return os;
}

template <class T>
ostream& operator<<(ostream& os, const vector<T>& v) {
    os << "{";
    rep(i, v.size()) {
        if (i) os << ",";
        os << v[i];
    }
    os << "}";
    return os;
}

#ifdef LOCAL
void debug_out() { cerr << endl; }
template <typename Head, typename... Tail>
void debug_out(Head H, Tail... T) {
    cerr << " " << H;
    debug_out(T...);
}
#define debug(...) \
    cerr << __LINE__ << " [" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)
#define dump(x) cerr << __LINE__ << " " << #x << " = " << (x) << endl
#else
#define debug(...) (void(0))
#define dump(x) (void(0))
#endif

const int maxn = 110;
const int maxs = 110;
constexpr ll INF = TEN(18);

int main() {
    int N;
    cin >> N;
    V<string> S(N);
    V<int> C(N);
    map<string, int> sid;
    sid[""] = 0;  // goal

    rep(i, N) {
        cin >> S[i] >> C[i];
        {
            string t;
            rep(j, S[i].size()) {
                t.pb(S[i][j]);
                if (!sid.count(t)) {
                    int sz = sid.size();
                    sid[t] = sz;
                }
            }
        }
        {
            string t;
            per(j, S[i].size()) {
                t = S[i][j] + t;
                if (!sid.count(t)) {
                    int sz = sid.size();
                    sid[t] = sz;
                }
            }
        }
    }

    int sz = sid.size();

    V<string> tos(sz);
    V<bool> is_pal(sz);
    for (auto p : sid) {
        tos[p.se] = p.fi;
        auto t = p.fi;
        reverse(ALL(t));
        is_pal[p.se] = (t == p.fi);
    }

    debug(tos);

    VV<ll> d(2, V<ll>(sz, INF));
    using Data = pair<ll, pii>;  // cost, (direction, string id)

    priority_queue<Data, V<Data>, greater<Data>> que;

    ll ans = INF;

    rep(i, N) {
        {
            auto t = S[i];
            reverse(ALL(t));
            if (S[i] == t) {
                chmin(ans, C[i]);
                continue;
            }
        }

        int id = sid[S[i]];
        rep(j, 2) {
            if (d[j][id] > C[i]) {
                d[j][id] = C[i];
                que.push(mp(C[i], mp(j, id)));
            }
        }
    }

    while (!que.empty()) {
        auto data = que.top();
        que.pop();
        int dir, id;
        tie(dir, id) = data.se;
        if (d[dir][id] < data.fi) continue;

        // debug(d[dir][id], tos[id], dir);

        rep(i, N) {  // another side
            string s = tos[id], t = S[i];
            if (dir) swap(s, t);  // s:left,t:right

            int l = 0;
            while (l < min(s.size(), t.size())) {
                if (s[l] == t[t.size() - 1 - l]) {
                    l++;
                } else {
                    break;
                }
            }
            // NG
            if (l < min(s.size(), t.size())) continue;
            // debug(s, t, l);

            ll nd = d[dir][id] + C[i];
            if (l == s.size() && l == t.size()) {
                chmin(ans, nd);
            } else if (l == s.size()) {
                string rem = t.substr(0, t.size() - l);
                debug(rem);
                int nid = sid[rem];
                if (is_pal[nid]) chmin(ans, nd);
                if (d[1][nid] > nd) {
                    d[1][nid] = nd;
                    que.push(mp(nd, mp(1, nid)));
                }
            } else {
                string rem = s.substr(l, s.size() - l);
                debug(rem);
                int nid = sid[rem];
                if (is_pal[nid]) chmin(ans, nd);
                if (d[0][nid] > nd) {
                    d[0][nid] = nd;
                    que.push(mp(nd, mp(0, nid)));
                }
            }
        }
    }

    if (ans == INF)
        cout << -1 << endl;
    else
        cout << ans << endl;

    return 0;
}

提出情報

提出日時	2020-08-13 22:24:48+0900
問題	F - Making Palindrome
ユーザ	satashun
言語	C++ (GCC 9.2.1)
得点	600
コード長	4898 Byte
結果	AC
実行時間	18 ms
メモリ	3812 KiB

コンパイルエラー

./Main.cpp: In function ‘int main()’:
./Main.cpp:17:41: warning: comparison of integer expressions of different signedness: ‘int’ and ‘std::__cxx11::basic_string<char>::size_type’ {aka ‘long unsigned int’} [-Wsign-compare]
   17 | #define rep2(i, m, n) for (int i = m; i < (n); i++)
      |                                         ^
./Main.cpp:16:19: note: in expansion of macro ‘rep2’
   16 | #define rep(i, n) rep2(i, 0, n)
      |                   ^~~~
./Main.cpp:82:13: note: in expansion of macro ‘rep’
   82 |             rep(j, S[i].size()) {
      |             ^~~
./Main.cpp:155:22: warning: comparison of integer expressions of different signedness: ‘int’ and ‘const long unsigned int’ [-Wsign-compare]
  155 |             while (l < min(s.size(), t.size())) {
      |                    ~~^~~~~~~~~~~~~~~~~~~~~~~~~
./Main.cpp:163:19: warning: comparison of integer expressions of different signedness: ‘int’ and ‘const long unsigned int’ [-Wsign-compare]
  163 |             if (l < min(s.size(), t.size())) continue;
      |                 ~~^~~~~~~~~~~~~~~~~~~~~~~~~
./Main.cpp:167:19: warning: comparison of integer expressions of different signedness: ‘int’ and ‘std::__cxx11::basic_string<char>::size_type’ {aka ‘long unsigned int’} [-Wsign-compare]
  167 |             if (l == s.size() && l == t.size()) {
      |                 ~~^~~~~~~~~~~
./Main.cpp:167:36: warning: comparison of integer expressions of different signedness: ‘int’ and ‘std::__cxx11::basic_string<char>::size_type’ {aka ‘long unsigned int’} [-Wsign-compare]
  167 |             if (l == s.size() && l == t.size()) {
      |                                  ~~^~~~~~~~~~~
./Main.cpp:169:26: warning: comparison of integer expressions of different signedness: ‘int’ and ‘std::__cxx11::basic_string<char>::size_type’ {aka ‘long unsigned int’} [-Wsign-compare]
  169 |             } else if (l == s.size()) {
      |                        ~~^~~~~~~~~~~

ジャッジ結果

セット名

Sample

All

after_contest

得点 / 配点

0 / 0

600 / 600

0 / 0

結果

× 4

× 59

× 1

セット名	テストケース
Sample	s1.txt, s2.txt, s3.txt, s4.txt
All	01.txt, 02.txt, 03.txt, 04.txt, 05.txt, 06.txt, 07.txt, 08.txt, 09.txt, 10.txt, 11.txt, 12.txt, 13.txt, 14.txt, 15.txt, 16.txt, 17.txt, 18.txt, 19.txt, 20.txt, 21.txt, 22.txt, 23.txt, 24.txt, 25.txt, 26.txt, 27.txt, 28.txt, 29.txt, 30.txt, 31.txt, 32.txt, 33.txt, 34.txt, 35.txt, 36.txt, 37.txt, 38.txt, 39.txt, 40.txt, 41.txt, 42.txt, 43.txt, 44.txt, 45.txt, 46.txt, 47.txt, 48.txt, 49.txt, 50.txt, 51.txt, 52.txt, 53.txt, 54.txt, after_contest_01.txt, s1.txt, s2.txt, s3.txt, s4.txt
after_contest	after_contest_01.txt

ケース名	結果	実行時間	メモリ
01.txt	AC	10 ms	3572 KiB
02.txt	AC	2 ms	3512 KiB
03.txt	AC	4 ms	3520 KiB
04.txt	AC	4 ms	3436 KiB
05.txt	AC	3 ms	3644 KiB
06.txt	AC	2 ms	3420 KiB
07.txt	AC	4 ms	3512 KiB
08.txt	AC	4 ms	3468 KiB
09.txt	AC	3 ms	3604 KiB
10.txt	AC	3 ms	3516 KiB
11.txt	AC	3 ms	3492 KiB
12.txt	AC	2 ms	3472 KiB
13.txt	AC	2 ms	3428 KiB
14.txt	AC	3 ms	3584 KiB
15.txt	AC	5 ms	3468 KiB
16.txt	AC	2 ms	3488 KiB
17.txt	AC	2 ms	3568 KiB
18.txt	AC	3 ms	3492 KiB
19.txt	AC	5 ms	3528 KiB
20.txt	AC	4 ms	3552 KiB
21.txt	AC	8 ms	3536 KiB
22.txt	AC	2 ms	3600 KiB
23.txt	AC	5 ms	3600 KiB
24.txt	AC	4 ms	3688 KiB
25.txt	AC	4 ms	3596 KiB
26.txt	AC	3 ms	3512 KiB
27.txt	AC	9 ms	3800 KiB
28.txt	AC	7 ms	3704 KiB
29.txt	AC	6 ms	3776 KiB
30.txt	AC	6 ms	3748 KiB
31.txt	AC	7 ms	3620 KiB
32.txt	AC	12 ms	3672 KiB
33.txt	AC	4 ms	3736 KiB
34.txt	AC	7 ms	3768 KiB
35.txt	AC	6 ms	3656 KiB
36.txt	AC	5 ms	3688 KiB
37.txt	AC	6 ms	3676 KiB
38.txt	AC	4 ms	3756 KiB
39.txt	AC	6 ms	3772 KiB
40.txt	AC	7 ms	3756 KiB
41.txt	AC	9 ms	3744 KiB
42.txt	AC	5 ms	3692 KiB
43.txt	AC	18 ms	3740 KiB
44.txt	AC	7 ms	3716 KiB
45.txt	AC	5 ms	3668 KiB
46.txt	AC	4 ms	3668 KiB
47.txt	AC	6 ms	3796 KiB
48.txt	AC	5 ms	3664 KiB
49.txt	AC	7 ms	3812 KiB
50.txt	AC	9 ms	3812 KiB
51.txt	AC	3 ms	3536 KiB
52.txt	AC	4 ms	3456 KiB
53.txt	AC	2 ms	3512 KiB
54.txt	AC	3 ms	3468 KiB
after_contest_01.txt	AC	5 ms	3496 KiB
s1.txt	AC	2 ms	3472 KiB
s2.txt	AC	3 ms	3564 KiB
s3.txt	AC	3 ms	3468 KiB
s4.txt	AC	2 ms	3500 KiB