oj.uz

답안 #1106344

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1106344 2024-10-30T03:18:06 Z Requiem Viruses (BOI20_viruses) C++17
100 / 100
 44 ms 11976 KB 
#include<bits/stdc++.h>
#define int long long
#define ull unsigned long long
#define pb push_back
#define fast ios_base::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
#define MOD 1000000007
#define inf 1e18
#define fi first
#define se second
#define FOR(i,a,b) for(int i=a;i<=b;i++)
#define FORD(i,a,b) for(int i=a;i>=b;i--)
#define sz(a) ((int)(a).size())
#define endl '\n'
#define pi 3.14159265359
#define TASKNAME "Viruses"
using namespace std;
template<typename T> bool maximize(T &res, const T &val) { if (res < val){ res = val; return true; }; return false; }
template<typename T> bool minimize(T &res, const T &val) { if (res > val){ res = val; return true; }; return false; }
typedef pair<int,int> ii;
typedef pair<int,ii> iii;
typedef vector<int> vi;
/**
Tóm tắt đề:
- Cho G gene, đánh số từ 0 đến G - 1.
- Cho N thao tác đột biến
Từ gene có chỉ số a, nó sẽ tạo thành 1 chuỗi gene mới có độ dài k x1 x2 x3 ... xk

Ta có M kháng thể ở dạng nhị phân.

VỚi từng số a từ 2 đến G - 1, ta muốn đột biến a cho đến khi:
- a trở thành 1 chuỗi nhị phân
- không chứa 1 chuỗi kháng thể nào.

Với những thằng biến đổi được thì xuất độ dài ngắn nhất
Ngược lại, xuất NO.

Sol chuẩn:
subtask 1 (M = 1):
Bài này ta sẽ giải bằng dijkstra / dp đại loại thế.

Ta xuất phát từ thằng x mà chưa được giải xong ta cập nhật 1 thằng bố của nó.

subtask 3 (M = 1):
Bây giờ có nhiều gene được tạo thành từ 1 con virus nên ta
cần phải decode nó thành 1 trạng thái.

dp_i_st_en: Số thằng đột biến từ gen i, xuất phát ở trạng thái st,
và kết thúc ở trạng thái en.

Giả sử ta có thao tác biến a --> <b1, b2, ..., bk>
dp_a_st_en = dp_b1_st_x1 + dp_b2_x1_x2 + dp_b3_x2_x3 + ... + dp_bk_xk-1_en.

Ta biến đổi như sau: 1 thao tác a --> <b1, b2, ..., bk> có thể
được biến đổi thành a --> <b1, z>
z là 1 gen mới và có khả năng z --> <b2, b3, ..., bk>

Trong trường hợp tệ nhất, số gene vẫn là O(G).

Bây giờ ta có thể chuyển trạng thái mượt mà hơn nhờ vào cái này.
a --> <b1>:
dp_i_st_en = min(dp_i_st_en, dp_b1_st_en).

a --> <b1, b2>:
dp_i_st_en = min(dp_i_st_en, di_b1_st_x1 + dp_b2_x1_en)

Nếu ta imple được cái thuật này thì độ phức tạp của nó sẽ là:
- Ta có O(S^2 * G) trạng thái
- Để chuyển trạng thái cho thằng kia, ta cần thêm 1 vòng for S nữa nên độ phức tạp là:
O(S^3 * G * log2(G * S^2)) nếu ta dijkstra.

Thế cái state ở đây là gì: state ở đây là độ khớp với 1 prefix của thằng kháng nguyên,
tức là ta muốn biết là ở độ khớp hiện tại.

Ta gọi dp_i_st_en: độ dài tối thiểu của con virus sao cho nó bắt đầu ở trạng thái khớp
tiền tố st của thằng antibody và kết thúc ở trạng thái khớp tiền tố độ dài l của thằng antibody.
**/

const int MAXN = 301;
int numGene = 0;
int numMutation = 0;
int numAntibody = 0;

int head[MAXN];

vector<int> mutation[MAXN];
vector<int> origin[MAXN];

string antibody[MAXN];

namespace subtask1{
    bool check(){
        return numAntibody == 0;
    }

    unsigned long long dp[MAXN];

    void solve(){
        FOR(i, 1, numMutation){
            for(auto p: mutation[i]){
                origin[p].pb(i);
            }
        }
        memset(dp, 0x3f, sizeof(dp));
        dp[1] = 1;
        dp[0] = 1;
        priority_queue<ii, vector<ii>, greater<ii>> pq;
        pq.push({1, 1});
        pq.push({1, 0});

        while(!pq.empty()){
            int du = pq.top().fi;
            int u = pq.top().se;
            pq.pop();

            if (du > dp[u]) continue;

            for(auto id: origin[u]){
                int a = head[id];
                int cur = 0;

                for(auto b: mutation[id]){
                    cur += dp[b];
                }

                if (minimize(dp[a], (ull) cur)){
                    pq.push({dp[a], a});
                }
            }
        }

        FOR(i, 2, numGene - 1){
            if (dp[i] < inf) cout << "NO " << dp[i] << endl;
            else cout << "YES" << endl;
        }
    }
}

namespace subtask3{
    bool check(){
        return numAntibody == 1;
    }

    ull dp[MAXN][51][51];
    int lps[MAXN], automata[MAXN][2];

    struct state{
        int id, st, en;
        int val;
        state(int _val = 0, int _id = 0, int _st = 0, int _en = 0){
            val = _val, st = _st, en = _en, id = _id;
        }
        bool operator < (const state &other) const {
            return val < other.val;
        }
    };

    void buildKMP(){
        int len = antibody[1].length();
        string anti = antibody[1];
        anti = '#' + anti + '#';

        FOR(i, 2, len){
            int j = lps[i - 1];
            while(j > 0 and anti[j + 1] != anti[i]) j = lps[j];

            if (anti[j + 1] == anti[i]) lps[i] = j + 1;
        }

        FOR(i, 0, len){
            FOR(c, 0, 1){
                if (anti[i + 1] - '0' == c) automata[i][c] = i + 1;
                else automata[i][c] = automata[lps[i]][c];
            }
        }
    }


    void solve(){
        set<pair<ii, ii>> pq;
        memset(dp, 0x3f, sizeof(dp));
        buildKMP();
        int tmp = numGene;

        FOR(i, 1, numMutation){
            while(mutation[i].size() > 2){
                int x2 = mutation[i].back();
                mutation[i].pop_back();
                int x1 = mutation[i].back();
                mutation[i].pop_back();

                mutation[++numMutation].pb(x1);
                mutation[numMutation].pb(x2);
                head[numMutation] = ++numGene;
                mutation[i].pb(numGene);
            }
        }
        FOR(i, 1, numMutation){
            for(int j = 0; j < mutation[i].size(); j++){
                origin[mutation[i][j]].pb(i);
            }
        }

        FOR(i, 0, 1){
            FOR(st, 0, antibody[1].length() - 1){
                int en = automata[st][i];
                if (en < antibody[1].length()) {
                    dp[i][st][en] = 1;
                    pq.insert({{1, i}, {st, en}});
                }
            }
        }
        int complexity = 0;
        while(!pq.empty()){
            pair<ii, ii> tp = *pq.begin();
            int u = tp.fi.se;
            int st = tp.se.fi;
            int en = tp.se.se;

            int du = tp.fi.fi;

            pq.erase(pq.begin());

            if (du > dp[u][st][en]) continue;
            complexity++;

            for(auto id: origin[u]){
                int a = head[id];
                if (mutation[id].size() == 1){
                    if (minimize(dp[a][st][en],(ull) du))
                        pq.insert({{du, a}, {st, en}});
                }
                else{
                    int other = ((mutation[id][0] == u) ? mutation[id][1] : mutation[id][0]);
                    FOR(third, 0, antibody[1].length() - 1){
                        if (mutation[id][0] == u) {

                            if (minimize(dp[a][st][third],(ull) du + dp[other][en][third])){
                                if (pq.find({{dp[a][st][third], a}, {st, third}}) == pq.end())
                                    pq.insert({{dp[a][st][third], a}, {st, third}});
                            }
                        }

                        if (mutation[id][1] == u){
                            if (minimize(dp[a][third][en], (ull) dp[other][third][st] + du)){
                                if (pq.find({{dp[a][third][en], a}, {third, en}}) == pq.end())
                                    pq.insert({{dp[a][third][en], a}, {third, en}});
                            }
                        }
                    }
                }
            }

        }
        FOR(i, 2, tmp - 1){
            ull ans = inf + 1;
            FOR(j, 0, (int) antibody[1].length() - 1){
                minimize(ans, dp[i][0][j]);
            }
            if (ans < inf) cout << "NO " << ans << endl;
            else cout << "YES \n";
        }

    }
}

namespace subtask5{
    bool check(){
        return true;
    }

    struct TrieNode{
        int child[2], suffixLink, depth, parent, bad;
        int automata[2];
        TrieNode(){
            suffixLink = 0;
            parent = 0;
            depth = 0;
            bad = false;
            memset(child, 0, sizeof(child));
            memset(automata, 0, sizeof(automata));
        }
    };

    struct Trie{
        vector<TrieNode> T = {TrieNode()};
        void addNum(string str){
            int p = 0;
            for(int i = 0; i < (int) str.length(); i++){
                int c = str[i] - '0';
                if (T[p].child[c] == 0){
                    T[p].child[c] = T.size();
                    T.pb(TrieNode());
                }

                T[T[p].child[c]].depth = T[p].depth + 1;
                T[T[p].child[c]].parent = p;

                p = T[p].child[c];
            }
            T[p].bad = true;
        }

        void constructAC(){
            queue<ii> q;
            q.push({0, -1});

            while(!q.empty()){
                int u = q.front().fi;
                int c = q.front().se;
                q.pop();

                if (T[u].depth <= 1) {
                    T[u].suffixLink = 0;
                }
                else{
                    int prv = T[T[u].parent].suffixLink;
                    while(prv > 0 and T[prv].child[c] == 0){
                        prv = T[prv].suffixLink;
                    }
                    if (T[prv].child[c] != 0) T[u].suffixLink = T[prv].child[c];
                }
                T[u].automata[0] = ((T[u].child[0] > 0) ? (T[u].child[0]) : (T[T[u].suffixLink].automata[0]));
                T[u].automata[1] = ((T[u].child[1] > 0) ? (T[u].child[1]) : (T[T[u].suffixLink].automata[1]));
                T[u].bad |= T[T[u].parent].bad;
                T[u].bad |= T[T[u].suffixLink].bad;

                for(int i = 0; i < 2; i++){
                    if (T[u].child[i] > 0) q.push({T[u].child[i], i});
                }
            }
        }


    };

    ull dp[MAXN][59][59];
    void solve(){
         Trie Trie;
         FOR(i, 1, numAntibody){
             Trie.addNum(antibody[i]);
         }
         Trie.constructAC();

//         FOR(i, 0, (int) Trie.T.size() - 1){
//            cout << i << ' ' << Trie.T[i].suffixLink << ' ' << Trie.T[i].bad << endl;
//         }

         int tmp = numGene;
         FOR(i, 1, numMutation){
             while(mutation[i].size() > 2){
                   int x2 = mutation[i].back();
                   mutation[i].pop_back();
                   int x1 = mutation[i].back();
                   mutation[i].pop_back();

                   mutation[++numMutation].pb(x1);
                   mutation[numMutation].pb(x2);

                   head[numMutation] = ++numGene;
                   mutation[i].pb(numGene);
             }
         }

         FOR(i, 1, numMutation){
             FOR(j, 0, (int) mutation[i].size() - 1){
                 origin[mutation[i][j]].pb(i);
             }
         }

         memset(dp, 0x3f, sizeof(dp));
         priority_queue<pair<ii, ii>, vector<pair<ii, ii>>, greater<pair<ii, ii>>> pq;

         FOR(i, 0, 1){
             FOR(j, 0, (int) Trie.T.size() - 1){
                if (Trie.T[j].bad) continue;

                int st = j;
                int en = Trie.T[j].automata[i];

                if (Trie.T[en].bad) continue;

                pq.push({{1,i} , {st,en}});
//                cerr << i << ' ' << st << ' ' << en << endl;
                dp[i][st][en] = 1;
             }
         }

         while(!pq.empty()){
             pair<ii, ii> tp = pq.top();
             int u = tp.fi.se;
             int st = tp.se.fi;
             int en = tp.se.se;
             int du = tp.fi.fi;
//             cerr << u << ' ' << st << ' ' << en << ' ' << du << endl;

             pq.pop();

             if (du > dp[u][st][en]) continue;

             for(auto id: origin[u]){
                 int a = head[id];

                 if (mutation[id].size() == 1){
                     if (minimize(dp[a][st][en], (ull) du)){
                         pq.push({{dp[a][st][en], a}, {st, en}});
                     }
                 }
                 else {
                     int other = ((mutation[id][0] == u) ? mutation[id][1] : mutation[id][0]);

                     FOR(third, 0, Trie.T.size() - 1){
                         if (mutation[id][0] == u){
                             if (minimize(dp[a][st][third], (ull) du + dp[other][en][third])){
                                 pq.push({ {dp[a][st][third], a} , {st, third} });
                             }
                         }

                         if (mutation[id][1] == u){
                             if (minimize(dp[a][third][en], (ull) dp[other][third][st] + du)){
                                 pq.push({  {dp[a][third][en], a}, {third, en} });
                             }
                         }
                     }
                 }
             }
         }


         FOR(i, 2, tmp - 1){
             ull ans = inf;
             FOR(j, 0, (int) Trie.T.size() - 1){
                 minimize(ans, dp[i][0][j]);
             }
             if (ans < inf) cout << "NO " << ans << endl;
             else cout << "YES" << endl;

         }


    }
}
main()
{
    fast;
    if (fopen(TASKNAME".inp","r")){
        freopen(TASKNAME".inp","r",stdin);
        freopen(TASKNAME".out","w",stdout);
    }
    cin >> numGene >> numMutation >> numAntibody;
    FOR(i, 1, numMutation){
        int a;
        int k;
        cin >> a >> k;
        head[i] = a;
        FOR(j, 0, k - 1){
            int x;
            cin >> x;
            mutation[i].pb(x);
        }
    }

    FOR(i, 1, numAntibody){
        int x;
        cin >> x;
        FOR(j, 0, x - 1){
            char c;
            cin >> c;
            antibody[i] = antibody[i] + c;
        }
    }

    if (subtask1::check()) return subtask1::solve(), 0;
    if (subtask3::check()) return subtask3::solve(), 0;
    if (subtask5::check()) return subtask5::solve(), 0;
}
/**
Warning:
Đọc sai đề???
Cận lmao
Code imple thiếu case nào không.
Limit.
**/

Compilation message

Viruses.cpp: In function 'void subtask1::solve()':
Viruses.cpp:115:20: warning: comparison of integer expressions of different signedness: 'long long int' and 'long long unsigned int' [-Wsign-compare]
  115 |             if (du > dp[u]) continue;
      |                 ~~~^~~~~~~
Viruses.cpp: In function 'void subtask3::solve()':
Viruses.cpp:198:30: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  198 |             for(int j = 0; j < mutation[i].size(); j++){
      |                            ~~^~~~~~~~~~~~~~~~~~~~
Viruses.cpp:10:33: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   10 | #define FOR(i,a,b) for(int i=a;i<=b;i++)
......
  204 |             FOR(st, 0, antibody[1].length() - 1){
      |                 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Viruses.cpp:204:13: note: in expansion of macro 'FOR'
  204 |             FOR(st, 0, antibody[1].length() - 1){
      |             ^~~
Viruses.cpp:206:24: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  206 |                 if (en < antibody[1].length()) {
      |                     ~~~^~~~~~~~~~~~~~~~~~~~~~
Viruses.cpp:223:20: warning: comparison of integer expressions of different signedness: 'long long int' and 'long long unsigned int' [-Wsign-compare]
  223 |             if (du > dp[u][st][en]) continue;
      |                 ~~~^~~~~~~~~~~~~~~
Viruses.cpp:10:33: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   10 | #define FOR(i,a,b) for(int i=a;i<=b;i++)
......
  234 |                     FOR(third, 0, antibody[1].length() - 1){
      |                         ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Viruses.cpp:234:21: note: in expansion of macro 'FOR'
  234 |                     FOR(third, 0, antibody[1].length() - 1){
      |                     ^~~
Viruses.cpp: In function 'void subtask5::solve()':
Viruses.cpp:398:21: warning: comparison of integer expressions of different signedness: 'long long int' and 'long long unsigned int' [-Wsign-compare]
  398 |              if (du > dp[u][st][en]) continue;
      |                  ~~~^~~~~~~~~~~~~~~
Viruses.cpp:10:33: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<subtask5::TrieNode>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   10 | #define FOR(i,a,b) for(int i=a;i<=b;i++)
......
  411 |                      FOR(third, 0, Trie.T.size() - 1){
      |                          ~~~~~~~~~~~~~~~~~~~~~~~~~~~
Viruses.cpp:411:22: note: in expansion of macro 'FOR'
  411 |                      FOR(third, 0, Trie.T.size() - 1){
      |                      ^~~
Viruses.cpp: At global scope:
Viruses.cpp:442:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
  442 | main()
      | ^~~~
Viruses.cpp: In function 'int main()':
Viruses.cpp:446:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  446 |         freopen(TASKNAME".inp","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
Viruses.cpp:447:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  447 |         freopen(TASKNAME".out","w",stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
11.0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Correct 1 ms 336 KB Output is correct
5 Correct 1 ms 336 KB Output is correct
6 Correct 1 ms 336 KB Output is correct
7 Correct 1 ms 336 KB Output is correct
8 Correct 1 ms 336 KB Output is correct
9 Correct 1 ms 336 KB Output is correct
10 Correct 1 ms 336 KB Output is correct
11 Correct 1 ms 508 KB Output is correct
12 Correct 1 ms 336 KB Output is correct
13 Correct 1 ms 336 KB Output is correct
14 Correct 1 ms 336 KB Output is correct
15 Correct 1 ms 336 KB Output is correct
16 Correct 1 ms 336 KB Output is correct
17 Correct 1 ms 508 KB Output is correct
18 Correct 1 ms 336 KB Output is correct
19 Correct 1 ms 336 KB Output is correct
20 Correct 1 ms 336 KB Output is correct

Subtask #2
14.0 / 14.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 3 ms 8696 KB Output is correct
4 Correct 3 ms 8528 KB Output is correct
5 Correct 3 ms 8272 KB Output is correct
6 Correct 3 ms 8528 KB Output is correct
7 Correct 4 ms 8528 KB Output is correct
8 Correct 3 ms 8528 KB Output is correct
9 Correct 3 ms 8272 KB Output is correct
10 Correct 2 ms 8784 KB Output is correct
11 Correct 2 ms 8784 KB Output is correct
12 Correct 2 ms 8952 KB Output is correct
13 Correct 2 ms 8864 KB Output is correct
14 Correct 2 ms 8784 KB Output is correct
15 Correct 2 ms 8784 KB Output is correct
16 Correct 2 ms 8784 KB Output is correct
17 Correct 2 ms 8784 KB Output is correct
18 Correct 3 ms 8784 KB Output is correct
19 Correct 2 ms 8956 KB Output is correct
20 Correct 2 ms 8784 KB Output is correct
21 Correct 2 ms 8784 KB Output is correct
22 Correct 2 ms 8784 KB Output is correct
23 Correct 2 ms 8784 KB Output is correct
24 Correct 2 ms 8784 KB Output is correct

Subtask #3
25.0 / 25.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 8696 KB Output is correct
2 Correct 3 ms 8528 KB Output is correct
3 Correct 3 ms 8272 KB Output is correct
4 Correct 3 ms 8528 KB Output is correct
5 Correct 4 ms 8528 KB Output is correct
6 Correct 3 ms 8528 KB Output is correct
7 Correct 3 ms 8272 KB Output is correct
8 Correct 3 ms 8272 KB Output is correct
9 Correct 2 ms 8272 KB Output is correct
10 Correct 3 ms 8272 KB Output is correct
11 Correct 3 ms 8272 KB Output is correct
12 Correct 3 ms 8272 KB Output is correct
13 Correct 3 ms 8272 KB Output is correct
14 Correct 2 ms 8272 KB Output is correct
15 Correct 3 ms 8272 KB Output is correct
16 Correct 3 ms 8272 KB Output is correct
17 Correct 3 ms 8272 KB Output is correct
18 Correct 3 ms 8528 KB Output is correct
19 Correct 2 ms 8272 KB Output is correct
20 Correct 3 ms 8272 KB Output is correct
21 Correct 3 ms 8272 KB Output is correct
22 Correct 3 ms 8272 KB Output is correct
23 Correct 2 ms 8496 KB Output is correct
24 Correct 2 ms 8272 KB Output is correct
25 Correct 9 ms 8528 KB Output is correct
26 Correct 2 ms 8752 KB Output is correct
27 Correct 44 ms 8952 KB Output is correct
28 Correct 4 ms 8528 KB Output is correct
29 Correct 34 ms 8584 KB Output is correct
30 Correct 37 ms 8528 KB Output is correct
31 Correct 7 ms 8528 KB Output is correct
32 Correct 4 ms 8528 KB Output is correct
33 Correct 4 ms 8272 KB Output is correct
34 Correct 34 ms 8696 KB Output is correct

Subtask #4
32.0 / 32.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Correct 1 ms 336 KB Output is correct
5 Correct 1 ms 336 KB Output is correct
6 Correct 1 ms 336 KB Output is correct
7 Correct 1 ms 336 KB Output is correct
8 Correct 1 ms 336 KB Output is correct
9 Correct 1 ms 336 KB Output is correct
10 Correct 1 ms 336 KB Output is correct
11 Correct 1 ms 508 KB Output is correct
12 Correct 1 ms 336 KB Output is correct
13 Correct 1 ms 336 KB Output is correct
14 Correct 1 ms 336 KB Output is correct
15 Correct 1 ms 336 KB Output is correct
16 Correct 1 ms 336 KB Output is correct
17 Correct 1 ms 508 KB Output is correct
18 Correct 1 ms 336 KB Output is correct
19 Correct 1 ms 336 KB Output is correct
20 Correct 1 ms 336 KB Output is correct
21 Correct 2 ms 8784 KB Output is correct
22 Correct 3 ms 8272 KB Output is correct
23 Correct 2 ms 8272 KB Output is correct
24 Correct 3 ms 8272 KB Output is correct
25 Correct 3 ms 8272 KB Output is correct
26 Correct 3 ms 8272 KB Output is correct
27 Correct 3 ms 8272 KB Output is correct
28 Correct 2 ms 8272 KB Output is correct
29 Correct 3 ms 8272 KB Output is correct
30 Correct 3 ms 8272 KB Output is correct
31 Correct 3 ms 8272 KB Output is correct
32 Correct 3 ms 8528 KB Output is correct
33 Correct 2 ms 8272 KB Output is correct
34 Correct 3 ms 8272 KB Output is correct
35 Correct 3 ms 8272 KB Output is correct
36 Correct 3 ms 8272 KB Output is correct
37 Correct 2 ms 8496 KB Output is correct
38 Correct 2 ms 8272 KB Output is correct
39 Correct 2 ms 8784 KB Output is correct
40 Correct 2 ms 8784 KB Output is correct
41 Correct 2 ms 8784 KB Output is correct
42 Correct 2 ms 8784 KB Output is correct
43 Correct 2 ms 8784 KB Output is correct
44 Correct 2 ms 8784 KB Output is correct
45 Correct 2 ms 8784 KB Output is correct
46 Correct 2 ms 8784 KB Output is correct
47 Correct 2 ms 8784 KB Output is correct
48 Correct 3 ms 8784 KB Output is correct
49 Correct 2 ms 8784 KB Output is correct
50 Correct 2 ms 8688 KB Output is correct
51 Correct 2 ms 8784 KB Output is correct
52 Correct 2 ms 8784 KB Output is correct
53 Correct 2 ms 8656 KB Output is correct
54 Correct 2 ms 8784 KB Output is correct
55 Correct 2 ms 8784 KB Output is correct

Subtask #5
18.0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 336 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Correct 1 ms 336 KB Output is correct
5 Correct 1 ms 336 KB Output is correct
6 Correct 1 ms 336 KB Output is correct
7 Correct 1 ms 336 KB Output is correct
8 Correct 1 ms 336 KB Output is correct
9 Correct 1 ms 336 KB Output is correct
10 Correct 1 ms 336 KB Output is correct
11 Correct 1 ms 508 KB Output is correct
12 Correct 1 ms 336 KB Output is correct
13 Correct 1 ms 336 KB Output is correct
14 Correct 1 ms 336 KB Output is correct
15 Correct 1 ms 336 KB Output is correct
16 Correct 1 ms 336 KB Output is correct
17 Correct 1 ms 508 KB Output is correct
18 Correct 1 ms 336 KB Output is correct
19 Correct 1 ms 336 KB Output is correct
20 Correct 1 ms 336 KB Output is correct
21 Correct 3 ms 8696 KB Output is correct
22 Correct 3 ms 8528 KB Output is correct
23 Correct 3 ms 8272 KB Output is correct
24 Correct 3 ms 8528 KB Output is correct
25 Correct 4 ms 8528 KB Output is correct
26 Correct 3 ms 8528 KB Output is correct
27 Correct 3 ms 8272 KB Output is correct
28 Correct 2 ms 8784 KB Output is correct
29 Correct 2 ms 8784 KB Output is correct
30 Correct 2 ms 8952 KB Output is correct
31 Correct 2 ms 8864 KB Output is correct
32 Correct 2 ms 8784 KB Output is correct
33 Correct 2 ms 8784 KB Output is correct
34 Correct 2 ms 8784 KB Output is correct
35 Correct 2 ms 8784 KB Output is correct
36 Correct 3 ms 8784 KB Output is correct
37 Correct 2 ms 8956 KB Output is correct
38 Correct 2 ms 8784 KB Output is correct
39 Correct 2 ms 8784 KB Output is correct
40 Correct 2 ms 8784 KB Output is correct
41 Correct 2 ms 8784 KB Output is correct
42 Correct 2 ms 8784 KB Output is correct
43 Correct 3 ms 8272 KB Output is correct
44 Correct 2 ms 8272 KB Output is correct
45 Correct 3 ms 8272 KB Output is correct
46 Correct 3 ms 8272 KB Output is correct
47 Correct 3 ms 8272 KB Output is correct
48 Correct 3 ms 8272 KB Output is correct
49 Correct 2 ms 8272 KB Output is correct
50 Correct 3 ms 8272 KB Output is correct
51 Correct 3 ms 8272 KB Output is correct
52 Correct 3 ms 8272 KB Output is correct
53 Correct 3 ms 8528 KB Output is correct
54 Correct 2 ms 8272 KB Output is correct
55 Correct 3 ms 8272 KB Output is correct
56 Correct 3 ms 8272 KB Output is correct
57 Correct 3 ms 8272 KB Output is correct
58 Correct 2 ms 8496 KB Output is correct
59 Correct 2 ms 8272 KB Output is correct
60 Correct 9 ms 8528 KB Output is correct
61 Correct 2 ms 8752 KB Output is correct
62 Correct 44 ms 8952 KB Output is correct
63 Correct 4 ms 8528 KB Output is correct
64 Correct 34 ms 8584 KB Output is correct
65 Correct 37 ms 8528 KB Output is correct
66 Correct 7 ms 8528 KB Output is correct
67 Correct 4 ms 8528 KB Output is correct
68 Correct 4 ms 8272 KB Output is correct
69 Correct 34 ms 8696 KB Output is correct
70 Correct 2 ms 8784 KB Output is correct
71 Correct 2 ms 8784 KB Output is correct
72 Correct 2 ms 8784 KB Output is correct
73 Correct 2 ms 8784 KB Output is correct
74 Correct 2 ms 8784 KB Output is correct
75 Correct 2 ms 8784 KB Output is correct
76 Correct 2 ms 8784 KB Output is correct
77 Correct 2 ms 8784 KB Output is correct
78 Correct 2 ms 8784 KB Output is correct
79 Correct 3 ms 8784 KB Output is correct
80 Correct 2 ms 8784 KB Output is correct
81 Correct 2 ms 8688 KB Output is correct
82 Correct 2 ms 8784 KB Output is correct
83 Correct 2 ms 8784 KB Output is correct
84 Correct 2 ms 8656 KB Output is correct
85 Correct 2 ms 8784 KB Output is correct
86 Correct 2 ms 8784 KB Output is correct
87 Correct 6 ms 9040 KB Output is correct
88 Correct 2 ms 8784 KB Output is correct
89 Correct 2 ms 8784 KB Output is correct
90 Correct 2 ms 8784 KB Output is correct
91 Correct 2 ms 8784 KB Output is correct
92 Correct 21 ms 11976 KB Output is correct
93 Correct 16 ms 9936 KB Output is correct
94 Correct 2 ms 8784 KB Output is correct
95 Correct 2 ms 8688 KB Output is correct
96 Correct 2 ms 8784 KB Output is correct
97 Correct 6 ms 9196 KB Output is correct
98 Correct 2 ms 8952 KB Output is correct
99 Correct 9 ms 8888 KB Output is correct
100 Correct 2 ms 8784 KB Output is correct
101 Correct 3 ms 8784 KB Output is correct
102 Correct 32 ms 9424 KB Output is correct
103 Correct 3 ms 8784 KB Output is correct
104 Correct 8 ms 8784 KB Output is correct
105 Correct 2 ms 8784 KB Output is correct
106 Correct 15 ms 9408 KB Output is correct
107 Correct 17 ms 9936 KB Output is correct