Submission #538452

#	Time	Username	Problem	Language	Result	Execution time	Memory
538452		abc864197532	Costinland (info1cup19_costinland)	C++17	100 / 100	1 ms	340 KiB

costinland

#include <bits/stdc++.h>
using namespace std;
#define lli long long int
#define mp make_pair
#define pb push_back
#define eb emplace_back
#define pii pair <int, int>
#define X first
#define Y second
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
void abc() {cout << endl;}
template <typename T, typename ...U> void abc(T a, U ...b) {
    cout << a << ' ', abc(b...);
}
template <typename T> void printv(T l, T r) {
    for (; l != r; ++l) cout << *l << " \n"[l + 1 == r];
}
template <typename A, typename B> istream& operator >> (istream& o, pair<A, B> &a) {
    return o >> a.X >> a.Y;
}
template <typename A, typename B> ostream& operator << (ostream& o, pair<A, B> a) {
    return o << '(' << a.X << ", " << a.Y << ')';
}
template <typename T> ostream& operator << (ostream& o, vector<T> a) {
    bool is = false;
    if (a.empty()) return o << "{}";
    for (T i : a) {o << (is ? ' ' : '{'), is = true, o << i;}
    return o << '}';
}
template <typename T> struct vv : vector <vector <T>> {
    vv(int n, int m, T v) : vector <vector <T>> (n, vector <T>(m, v)) {}
    vv() {}
};
template <typename T> struct vvv : vector <vv <T>> {
    vvv(int n, int m, int k, T v) : vector <vv <T>> (n, vv <T>(m, k, v)) {}
    vvv() {}
};
#ifdef Doludu
#define test(args...) abc("[" + string(#args) + "]", args)
#define owo freopen("input.txt", "r", stdin), freopen("output.txt", "w", stdout); 
#else
#define test(args...) void(0)
#define owo ios::sync_with_stdio(false); cin.tie(0)
#endif
const int mod = 1e9 + 7, N = 1e5 + 87, logN = 20, K = 111, M = N * 20;

int v[8] = {1, 3, 9, 23, 1, 5, 13, 27}, v2[6] = {1, 2, 6, 1, 4, 8};
int val[50], val2[20];

int main () {
    owo;
    for (int s = 0; s < 1 << 8; ++s) {
        int sum = 0;
        for (int i = 0; i < 8; ++i) if (s >> i & 1)
            sum += v[i];
        if (sum < 50)
            val[sum] = s;
    }
    val[4] = 3;
    for (int s = 0; s < 1 << 6; ++s) {
        int sum = 0;
        for (int i = 0; i < 6; ++i) if (s >> i & 1)
            sum += v2[i];
        if (sum < 20)
            val2[sum] = s;
    }
    val2[3] = 3;
    lli T;
    cin >> T;
    if (T <= 19) {
        int n = 5, m = 5;
        vector <array <int, 4>> ans;
        ans.pb({2, 2, 3, 2});
        int s = val2[T], mxd = -1, mxr = -1;
        for (int i = 0; i < 3; ++i) if (s >> i & 1)
            mxd = i;
        for (int i = 0; i < 3; ++i) if (s >> i + 3 & 1)
            mxr = i;
        if (mxd != -1)
            mxd += n - 4;
        if (mxr != -1)
            mxr += m - 4;
        for (int i = 0; i < 6; ++i) if (~s >> i & 1) {
            if (i < 3)
                ans.pb({n - 1, m - 4 + i, n, m - 4 + i});
            else
                ans.pb({n - 7 + i, m - 1, n - 7 + i, m});
        }
        if (mxd == -1) {
            for (int i = m - 4; i <= m - 1; ++i)
                ans.pb({mxr, i, mxr + 1, i});
        } else if (mxr == -1) {
            if (mxd != n - 3) {
                for (int i = n - 4; i <= n - 1; ++i)
                    ans.pb({i, mxd, i, mxd + 1});
            } else {
                for (int i = n - 4; i < n - 2; ++i)
                    ans.pb({i, mxd - 1, i, mxd});
                for (int i = n - 2; i <= n - 1; ++i)
                    ans.pb({i, mxd, i, mxd + 1});
            }
        } else {
            for (int i = mxd + 1; i <= m - 1; ++i)
                ans.pb({mxr, i, mxr + 1, i});
            for (int i = mxr + 1; i <= n - 1; ++i)
                ans.pb({i, mxd, i, mxd + 1});
        }
        cout << n << ' ' << m << '\n';
        vv <int> d(n, m, true), r(n, m, true);
        for (auto &i : ans) {
            if (i[0] + 1 == i[2])
                d[--i[0]][--i[1]] = false;
            else
                r[--i[0]][--i[1]] = false;
        }
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < m; ++j) {
                if (i == n - 1 && j == m - 1)
                    cout << '.';
                else if (i == n - 1)
                    cout << 'r';
                else if (j == m - 1)
                    cout << 'd';
                else if (d[i][j] && r[i][j])
                    cout << 'X';
                else if (d[i][j])
                    cout << 'd';
                else
                    cout << 'r';
            }
            cout << '\n';
        }
        return 0;
    }
    vector <array <int, 4>> ans;
    int n = 45, m = 45;
    for (int i = 0; i <= 40; i += 4) {
        ans.pb({i + 2, i + 2, i + 3, i + 2});
        for (int c = i + 1; c <= i + (i == 40 ? 3 : 4); ++c) {
            for (int r = i + 6; r < n; ++r) {
                ans.pb({r, c, r, c + 1});
                ans.pb({c, r, c + 1, r});
            }
        }
    }
    int now = 0, pres = -1;
    for (int now = 0; now <= 40; now += 4, T /= 50) {
        if (T == 0) {
            int mxd = -1, mxr = -1;
            for (int i = 0; i < 4; ++i) if (pres >> i & 1)
                mxd = i;
            for (int i = 0; i < 4; ++i) if (pres >> i + 4 & 1)
                mxr = i;
            if (mxd != -1)
                mxd += now - 4;
            if (mxr != -1)
                mxr += now - 4;
            if (mxd == -1) {
                for (int i = now - 3; i <= now + 1; ++i)
                    ans.pb({mxr + 1, i, mxr + 2, i});
            } else if (mxr == -1) {
                if (mxd % 4 != 1) {
                    for (int i = now - 3; i <= now + 1; ++i)
                        ans.pb({i, mxd + 1, i, mxd + 2});
                } else {
                    for (int i = now - 3; i < now - 1; ++i)
                        ans.pb({i, mxd, i, mxd + 1});
                    for (int i = now - 1; i <= now + 1; ++i)
                        ans.pb({i, mxd + 1, i, mxd + 2});
                }
            } else {
                for (int i = mxd + 2; i <= now + 1; ++i)
                    ans.pb({mxr + 1, i, mxr + 2, i});
                for (int i = mxr + 2; i <= now + 1; ++i)
                    ans.pb({i, mxd + 1, i, mxd + 2});
            }
            break;
        }
        if (now == 40)
            break;
        int s = val[T % 50];
        for (int i = 0; i < 8; ++i) if (~s >> i & 1) {
            if (i < 4) {
                ans.pb({now + 5, now + i + 1, now + 6, now + i + 1});
            } else {
                ans.pb({now + i - 4 + 1, now + 5, now + i - 4 + 1, now + 6});
            }
        }
        pres = s;
    }
    if (T) {
        int s = val2[T], mxd = -1, mxr = -1;
        for (int i = 0; i < 3; ++i) if (s >> i & 1)
            mxd = i;
        for (int i = 0; i < 3; ++i) if (s >> i + 3 & 1)
            mxr = i;
        if (mxd != -1)
            mxd += n - 4;
        if (mxr != -1)
            mxr += m - 4;
        for (int i = 0; i < 6; ++i) if (~s >> i & 1) {
            if (i < 3)
                ans.pb({n - 1, m - 4 + i, n, m - 4 + i});
            else
                ans.pb({n - 7 + i, m - 1, n - 7 + i, m});
        }
        if (mxd == -1) {
            for (int i = m - 4; i <= m - 1; ++i)
                ans.pb({mxr, i, mxr + 1, i});
        } else if (mxr == -1) {
            if (mxd != n - 3) {
                for (int i = n - 4; i <= n - 1; ++i)
                    ans.pb({i, mxd, i, mxd + 1});
            } else {
                for (int i = n - 4; i < n - 2; ++i)
                    ans.pb({i, mxd - 1, i, mxd});
                for (int i = n - 2; i <= n - 1; ++i)
                    ans.pb({i, mxd, i, mxd + 1});
            }
        } else {
            for (int i = mxd + 1; i <= m - 1; ++i)
                ans.pb({mxr, i, mxr + 1, i});
            for (int i = mxr + 1; i <= n - 1; ++i)
                ans.pb({i, mxd, i, mxd + 1});
        }
    }
    cout << n << ' ' << m << '\n';
    vv <int> d(n, m, true), r(n, m, true);
    for (auto &i : ans) {
        if (i[0] + 1 == i[2])
            d[--i[0]][--i[1]] = false;
        else
            r[--i[0]][--i[1]] = false;
    }
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < m; ++j) {
            if (i == n - 1 && j == m - 1)
                cout << '.';
            else if (i == n - 1)
                cout << 'r';
            else if (j == m - 1)
                cout << 'd';
            else if (d[i][j] && r[i][j])
                cout << 'X';
            else if (d[i][j])
                cout << 'd';
            else
                cout << 'r';
        }
        cout << '\n';
    }
}

Compilation message (stderr)

costinland.cpp: In function 'int main()':
costinland.cpp:78:48: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   78 |         for (int i = 0; i < 3; ++i) if (s >> i + 3 & 1)
      |                                              ~~^~~
costinland.cpp:153:55: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  153 |             for (int i = 0; i < 4; ++i) if (pres >> i + 4 & 1)
      |                                                     ~~^~~
costinland.cpp:196:48: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  196 |         for (int i = 0; i < 3; ++i) if (s >> i + 3 & 1)
      |                                              ~~^~~
costinland.cpp:147:9: warning: unused variable 'now' [-Wunused-variable]
  147 |     int now = 0, pres = -1;
      |         ^~~

• Subtask 1: 20 / 20
• Subtask 2: 80 / 80