Submission #1362737

#TimeUsernameProblemLanguageResultExecution timeMemory
1362737iamhereforfunRemittance (JOI19_remittance)C++20
15 / 100
4 ms6468 KiB
// Starcraft 2 enjoyer //

#include <bits/stdc++.h>

// #pragma GCC target("avx2")
// #pragma GCC optimize("O3")
// #pragma GCC optimize("unroll-loops")

using namespace std;

#define LSOne(X) ((X) & -(X))

const int N = 7;
const int M = 6e6 + 5;
const int B = 18;
const long long K = 2;
const int LG = 20;
const int INF = 1e9 + 5;
const int P = 31;
const int MOD = 1e9 + 7;
const int nx[] = {0, 1, 0, -1}, ny[] = {-1, 0, 1, 0};

int n, a[N], b[N], i, c, cur[N], pw[N], ptr[M];
bool chk[M];

int val(int *cur)
{
    i = 0;
    c = 1;
    for (int x = 0; x < n; x++)
    {
        i += cur[x] * c;
        c *= 9;
    }
    return i;
}

void dfs(int a)
{
    int tmp[n];
    chk[a] = 1;
    for (int x = 0; x < n; x++)
    {
        tmp[x] = cur[x];
    }
    for (int x = n - 1; x >= 0; x--)
    {
        cur[x] = (a / pw[x]);
        a -= (a / pw[x]) * pw[x];
    }
    for (int x = 0; x < n; x++)
    {
        if (cur[x] >= 2)
        {
            cur[x] -= 2;
            cur[(x + 1) % n]++;
            if (!chk[val(cur)])
            {
                ptr[val(cur)] = val(tmp);
                dfs(val(cur));
            }
            cur[x] += 2;
            cur[(x + 1) % n]--;
        }
    }
    for (int x = 0; x < n; x++)
    {
        cur[x] = tmp[x];
    }
}

inline void solve()
{
    cin >> n;
    i = 0;
    c = 1;
    for (int x = 0; x < n; x++)
    {
        cin >> a[x] >> b[x];
        i += a[x] * c;
        pw[x] = c;
        c *= 9;
    }
    chk[i] = 1;
    ptr[i] = -1;
    dfs(i);
    for (int x = 0; x < n; x++)
    {
        cur[x] = b[x];
    }
    int i = val(cur);
    if (chk[val(cur)])
    {
        // int cnt = 0;
        // while (i != -1)
        // {
        //     // if (cnt > 10)
        //     //     break;
        //     cnt++;
        //     // for (int x = 0; x < n; x++)
        //     // {
        //     //     cout << cur[x] << " ";
        //     // }
        //     // cout << "\n";
        //     // cout << i << "\n";
        //     i = ptr[i];
        //     if (i == -1)
        //         break;
        //     int a = i;
        //     for (int x = n - 1; x >= 0; x--)
        //     {
        //         cur[x] = (i / pw[x]);
        //         i -= (i / pw[x]) * pw[x];
        //     }
        //     i = a;
        // }
        cout << "Yes\n";
    }
    else
    {
        cout << "No\n";
    }
}

signed main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int t = 1;
    // cin >> t;
    for (int x = 1; x <= t; x++)
    {
        solve();
    }
    return 0;
}
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...
#Result Execution timeMemoryGrader output
Fetching results...