oj.uz

Submission #439452

# Submission time Handle Problem Language Result Execution time Memory
439452 2021-06-30T03:26:17 Z anmolagarwal Vlak (COCI20_vlak) C++17
70 / 70
 28 ms 21428 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const LL MOD = 1000000007;
#define pb push_back
#define all(c) (c).begin(), (c).end()
#define debug(x) cout << #x << " : " << x << endl
#define part cout << "----------------------------------\n";
#include <iostream>

int dx[] = {1, 1, 0, -1, -1, -1, 0, 1}; // trick to explore an implicit 2D grid
int dy[] = {0, 1, 1, 1, 0, -1, -1, -1}; // S,SE,E,NE,N,NW,W,SW neighbors  //GO FOR EVEN FOR 4 moves

#define fastinput                     \
    ios_base::sync_with_stdio(false); \
    cin.tie(NULL);                    \
    cout.tie(NULL);

vector<string> s[2];
//2 tries
struct node
{
    int arr[2][26];
    int id;
};
vector<node *> v;

node *get_node()
{
    node *a = new node;
    for (int i = 0; i < 2; i++)
    {
        for (int j = 0; j < 26; j++)
        {
            a->arr[i][j] = -1;
        }
    }
    a->id = v.size();
    return a;
}

void insert(string s, int person)
{
    int i, j, k;
    // cout << "inserting " << s << " for " << person << endl;
    node *curr_node = v[0];
    // cout << "v[0] is " << endl;
    // for (i = 0; i < 3; i++)
    // {
        // cout << v[0]->arr[person][i] << endl;
    // }
    // cout << "\n";
    for (auto &x : s)
    {
        int char_id = x - 'a';
        // cout << "curr node id is " << curr_node->id << endl;
        // cout << ((curr_node == v[0]) ? 1:0) << endl;
        if (curr_node->arr[person][char_id] == -1)
        {
            //make new node
            if (curr_node->arr[1 - person][char_id] == -1)
            {
                // cout << "did not find " << x << endl;
                curr_node->arr[person][char_id] = v.size();
                v.pb(get_node());
            }
            else
            {
                curr_node->arr[person][char_id] = curr_node->arr[1 - person][char_id];
            }
        }
        else
        {
            // cout << "found " << x << endl;
        }
        // debug(curr_node->arr[person][char_id]);
        // debug(v.size());
        assert(curr_node->arr[person][char_id] < v.size());
        curr_node = (v[curr_node->arr[person][char_id]]);
    }

    // cout << "AGAIN v[0] is " << endl;
    // for (i = 0; i < 3; i++)
    // {
        // cout << v[0]->arr[person][i] << endl;
    // }
    // cout << "\n";
    // part;
}

bool is_winning(int person_turn, node *curr_node)
{
    //must be losing for other person
    // bool curr_stat = false;
    // debug(person_turn);
    for (int i = 0; i < 26; i++)
    {
        if (curr_node->arr[person_turn][i] != -1)
        {
            // debug(i);
            bool stat = is_winning(person_turn ^ 1, v[curr_node->arr[person_turn][i]]);
            // cout << "node at " << (char)(i + 'a') << " returned " << stat << endl;
            if (stat == false)
            {
                return true;
            }
        }
    }

    return false;
}

struct node *root = get_node();
int main()
{
    fastinput;
    LL n, i, j, k, temp, tc;
    int num1, num2;
    cin >> num1;
    v.pb(root);
    for (i = 0; i < num1; i++)
    {
        string t;
        cin >> t;
        s[0].pb(t);
        insert(t, 0);
    }
    // return 0;
    cin >> num2;
    for (i = 0; i < num2; i++)
    {
        string t;
        cin >> t;
        s[1].pb(t);
        insert(t, 1);
    }
    //////////////////////////////////
    // debug(v.size());

    bool final = is_winning(0, v[0]);
    if (final)
    {
        cout << "Nina" << endl;
    }
    else
    {
        cout << "Emilija" << endl;
    }

    return 0;
}

Compilation message

In file included from /usr/include/c++/10/cassert:44,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:33,
                 from Main.cpp:1:
Main.cpp: In function 'void insert(std::string, int)':
Main.cpp:78:48: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<node*>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   78 |         assert(curr_node->arr[person][char_id] < v.size());
      |                ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~
Main.cpp:44:9: warning: unused variable 'i' [-Wunused-variable]
   44 |     int i, j, k;
      |         ^
Main.cpp:44:12: warning: unused variable 'j' [-Wunused-variable]
   44 |     int i, j, k;
      |            ^
Main.cpp:44:15: warning: unused variable 'k' [-Wunused-variable]
   44 |     int i, j, k;
      |               ^
Main.cpp: In function 'int main()':
Main.cpp:117:8: warning: unused variable 'n' [-Wunused-variable]
  117 |     LL n, i, j, k, temp, tc;
      |        ^
Main.cpp:117:14: warning: unused variable 'j' [-Wunused-variable]
  117 |     LL n, i, j, k, temp, tc;
      |              ^
Main.cpp:117:17: warning: unused variable 'k' [-Wunused-variable]
  117 |     LL n, i, j, k, temp, tc;
      |                 ^
Main.cpp:117:20: warning: unused variable 'temp' [-Wunused-variable]
  117 |     LL n, i, j, k, temp, tc;
      |                    ^~~~
Main.cpp:117:26: warning: unused variable 'tc' [-Wunused-variable]
  117 |     LL n, i, j, k, temp, tc;
      |                          ^~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 460 KB Output is correct
2 Correct 1 ms 588 KB Output is correct
3 Correct 1 ms 568 KB Output is correct
4 Correct 1 ms 460 KB Output is correct

Subtask #2
10.0 / 10.0

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

Subtask #3
10.0 / 10.0

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

Subtask #4
10.0 / 10.0

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

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 20428 KB Output is correct
2 Correct 25 ms 19124 KB Output is correct
3 Correct 25 ms 18044 KB Output is correct
4 Correct 28 ms 19904 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 27 ms 20548 KB Output is correct
2 Correct 22 ms 21428 KB Output is correct
3 Correct 22 ms 19840 KB Output is correct
4 Correct 22 ms 20164 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 19616 KB Output is correct
2 Correct 28 ms 19136 KB Output is correct
3 Correct 24 ms 19648 KB Output is correct
4 Correct 22 ms 20920 KB Output is correct