Submission #54634059

Source Code Expand

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
//#pragma GCC optimize("Ofast,unroll-loops")
//#pragma GCC target("sse4.2,abm,bmi,bmi2,popcnt,lzcnt,avx,avx2,fma")
#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
#include <iomanip>
#include <set>
#include <stack>
#include <map>
#include <list>
#include <string>
#include <cstring>
#include <cstdlib>
#include <cctype>
#include <fstream>
#include <ios>
#include <signal.h>
#include <queue>
#include <ctime>
#include <bitset>
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX

//#pragma GCC optimize("Ofast,unroll-loops")
//#pragma GCC target("sse4.2,abm,bmi,bmi2,popcnt,lzcnt,avx,avx2,fma")
#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
#include <iomanip>
#include <set>
#include <stack>
#include <map>
#include <list>
#include <string>
#include <cstring>
#include <cstdlib>
#include <cctype>
#include <fstream>
#include <ios>
#include <signal.h>
#include <queue>
#include <ctime>
#include <bitset>
#include <unordered_map>
#include <random>
#include <unordered_set>
#include <functional>
//#include <windows.h>
//#include "Header.h"
//#define f first
//#define s second

typedef long long ll;
typedef unsigned long long ull;

using namespace std;

ll GCD(ll a, ll b) {
    if (b > a) {
        swap(a, b);
    }
    if (a < 0 || b < 0) {
        return a >= 0 ? a : b;
    }
    while (b != 0 && a != b) {
        ll t = b;
        b = a % b;
        a = t;
    }
    return a;
}

pair<ll, ll> GCDEX(ll a, ll b) {
    bool flag = true;
    if (b > a) {
        swap(a, b);
        flag = false;
    }
    ll x1 = 1, y1 = 0, x2 = 0, y2 = 1, tx, ty;
    while (b != 0 && a != b) {
        tx = x1 - (a / b) * x2, ty = y1 - (a / b) * y2;
        x1 = x2, y1 = y2, x2 = tx, y2 = ty;
        ll t = b;
        b = a % b;
        a = t;
    }
    if (!flag) {
        ll temp = x1;
        x1 = y1;
        y1 = temp;
    }
    return { x1, y1 };
}

ll bpow(ll n, ll a, const ll mod) { return n == 0 ? 1 : n & 1 ? a * (bpow(n - 1, a, mod) % mod) % mod : bpow(n >> 1, a * (a % mod) % mod, mod); }

const int SIZE = 65;

int main(int argc, char* argv[]) {
    //SetConsoleCP(1251);
    //SetConsoleOutputCP(1251);
    //freopen("input.txt", "r", stdin);
    //freopen("output.txt", "w", stdout);
    //string alf = "abcdefghijklmnopqrstuvwxyz";
    //srand(time(0));
    //const double PI = 3.1415926535897932;
    //hash<string> hasher;
    const double eps = 0.000000001;
    const long long mod = 998244353;
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    ll n, cur = 0, cnt = 0, cnt1 = 0, cnt2 = 0;
    set<tuple<ll, ll, ll> > st;
    pair<ll, ll> temp = { 19, 0 };
    vector<string> ans1, ans2;
    bool flag = true;
    cin >> n;
    vector<vector<ll> > v(n, vector<ll>(n)), vv;
    vector<pair<ll, ll> > str(n, {-1, -1});
    for (ll i = 0; i < n; ++i) {
        for (ll j = 0; j < n; ++j) {
            cin >> v[i][j];
            if (v[i][j] < 0) {
                st.insert({ -v[i][j], i, j });
            }
            else {
                if (str[i].first == -1) {
                    str[i].first = j;
                }
                str[i].second = j;
                ++cnt;
            }
        }
    }
    vv = v;
    for (ll i = 0; i < n; ++i) {
        for (ll j = (i % 2 == 0 ? 0 : n - 1); (j < n && j >= 0); j += (i % 2 == 0 ? 1 : -1)) {
            if (v[i][j] > 0) {
                cur += v[i][j];
                //cout << '+' << v[i][j] << '\n';
                ans1.push_back("+" + to_string(v[i][j]));
                v[i][j] = 0;
            }
            else if (v[i][j]) {
                if (cur >= -v[i][j]) {
                    //cout << '-' << -v[i][j] << '\n';
                    ans1.push_back("-" + to_string(-v[i][j]));
                    cur += v[i][j];
                    st.erase({ -v[i][j], i, j });
                    v[i][j] = 0;
                }
            }
            if (i % 2 == 0 && j != n - 1) {
                //cout << 'R' << '\n';
                ans1.push_back("R");
            }
            else if (i % 2 == 1 && j != 0) {
                //cout << 'L' << '\n';
                ans1.push_back("L");
            }
        }
        if (i != n - 1) {
            //cout << 'D' << '\n';
            ans1.push_back("D");
        }
    }
    while (st.size()) {
        ll mn = 1e18;
        pair<ll, ll> pt;
        set<tuple<ll, ll, ll> >::iterator it1 = st.begin(), it = st.begin();
        while (it != st.end()) {
            if (abs(get<1>(*it) - temp.first) + abs(get<2>(*it) - temp.second) < mn) {
                mn = abs(get<1>(*it) - temp.first) + abs(get<2>(*it) - temp.second);
                pt = { get<1>(*it), get<2>(*it) };
                it1 = it;
            }
            ++it;
        }
        while (pt.first > temp.first) {
            ++temp.first;
            //cout << 'D' << '\n';
            ans1.push_back("D");
        }
        while (pt.first < temp.first) {
            --temp.first;
            //cout << 'U' << '\n';
            ans1.push_back("U");
        }
        while (pt.second > temp.second) {
            ++temp.second;
            //cout << 'R' << '\n';
            ans1.push_back("R");
        }
        while (pt.second < temp.second) {
            --temp.second;
            //cout << 'L' << '\n';
            ans1.push_back("L");
        }
        if (cur >= -v[temp.first][temp.second]) {
            //cout << '-' << -v[temp.first][temp.second] << '\n';
            ans1.push_back("-" + to_string(-v[temp.first][temp.second]));
            cur += v[temp.first][temp.second];
            v[temp.first][temp.second] = 0;
        }
        st.erase(it1);
    }
    v = vv;
    temp = { 0, 19 };
    for (ll i = 0; i < n; ++i) {
        for (ll j = 0; j < n; ++j) {
            if (v[i][j] < 0) {
                st.insert({ -v[i][j], i, j });
            }
            else {
                if (str[i].first == -1) {
                    str[i].first = j;
                }
                str[i].second = j;
                ++cnt;
            }
        }
    }
    for (ll j = 0; j < n; ++j) {
        for (ll i = (j % 2 == 0 ? 0 : n - 1); (i < n && i >= 0); i += (j % 2 == 0 ? 1 : -1)) {
            if (v[i][j] > 0) {
                cur += v[i][j];
                //cout << '+' << v[i][j] << '\n';
                ans2.push_back("+" + to_string(v[i][j]));
                v[i][j] = 0;
            }
            else if (v[i][j]) {
                if (cur >= -v[i][j]) {
                    //cout << '-' << -v[i][j] << '\n';
                    ans2.push_back("-" + to_string(-v[i][j]));
                    cur += v[i][j];
                    st.erase({ -v[i][j], i, j });
                    v[i][j] = 0;
                }
            }
            if (j % 2 == 0 && i != n - 1) {
                //cout << 'R' << '\n';
                ans2.push_back("D");
            }
            else if (j % 2 == 1 && i != 0) {
                //cout << 'L' << '\n';
                ans2.push_back("U");
            }
        }
        if (j != n - 1) {
            //cout << 'D' << '\n';
            ans2.push_back("R");
        }
    }
    while (st.size()) {
        ll mn = 1e18;
        pair<ll, ll> pt;
        set<tuple<ll, ll, ll> >::iterator it1 = st.begin(), it = st.begin();
        while (it != st.end()) {
            if (abs(get<1>(*it) - temp.first) + abs(get<2>(*it) - temp.second) < mn) {
                mn = abs(get<1>(*it) - temp.first) + abs(get<2>(*it) - temp.second);
                pt = { get<1>(*it), get<2>(*it) };
                it1 = it;
            }
            ++it;
        }
        while (pt.first > temp.first) {
            ++temp.first;
            //cout << 'D' << '\n';
            ans2.push_back("D");
        }
        while (pt.first < temp.first) {
            --temp.first;
            //cout << 'U' << '\n';
            ans2.push_back("U");
        }
        while (pt.second > temp.second) {
            ++temp.second;
            //cout << 'R' << '\n';
            ans2.push_back("R");
        }
        while (pt.second < temp.second) {
            --temp.second;
            //cout << 'L' << '\n';
            ans2.push_back("L");
        }
        if (cur >= -v[temp.first][temp.second]) {
            //cout << '-' << -v[temp.first][temp.second] << '\n';
            ans2.push_back("-" + to_string(-v[temp.first][temp.second]));
            cur += v[temp.first][temp.second];
            v[temp.first][temp.second] = 0;
        }
        st.erase(it1);
    }
    if (ans1.size() < ans2.size()) {
        for (string s : ans1) {
            cout << s << '\n';
        }
    }
    else {
        for (string s : ans2) {
            cout << s << '\n';
        }
    }
    return 0;
}

/*
20
10 4 0 0 4 10 16 20 21 16 11 2 -7 -16 -23 -25 -23 -16 -7 2
16 10 6 5 7 10 13 15 14 10 4 -4 -13 -21 -29 -32 -29 -22 -13 -3
20 14 10 8 9 10 11 12 10 6 0 -7 -15 -24 -31 -33 -31 -25 -16 -8
20 15 12 10 10 10 10 11 8 5 0 -5 -12 -20 -26 -29 -28 -23 -15 -7
16 13 12 10 10 10 10 10 9 7 4 1 -4 -10 -16 -20 -20 -17 -10 -3
10 10 10 10 11 10 10 10 10 10 10 9 7 2 -3 -8 -9 -8 -3 3
4 7 9 10 10 10 10 10 11 14 16 18 17 14 9 5 1 1 4 9
0 5 8 10 10 10 10 10 12 15 20 24 25 24 19 14 9 7 9 13
0 6 10 12 11 11 9 9 10 14 20 26 29 28 24 18 13 10 10 14
4 10 14 16 13 10 7 5 6 10 16 23 26 26 23 16 10 8 6 10
11 16 20 21 16 10 4 0 0 4 10 16 21 20 16 10 4 0 1 4
16 23 26 24 18 9 1 -4 -7 -4 2 9 12 12 8 3 -3 -6 -7 -3
20 26 27 24 17 7 -3 -11 -14 -12 -7 -1 2 2 -1 -5 -10 -12 -11 -7
20 24 24 20 13 3 -8 -17 -21 -20 -16 -12 -9 -9 -11 -14 -15 -15 -12 -6
16 18 17 14 6 -3 -13 -20 -24 -25 -23 -21 -20 -19 -21 -21 -18 -15 -10 -3
10 10 8 4 -1 -8 -14 -20 -23 -25 -25 -26 -27 -28 -28 -25 -21 -14 -5 3
4 2 -1 -4 -7 -9 -12 -15 -18 -19 -23 -26 -29 -31 -31 -28 -21 -11 -1 8
0 -4 -7 -9 -9 -8 -7 -7 -8 -11 -16 -20 -26 -30 -31 -28 -20 -8 2 12
0 -6 -9 -10 -7 -3 1 3 3 -1 -7 -13 -20 -26 -29 -27 -20 -9 2 13
4 -3 -6 -6 -3 3 9 12 12 9 3 -5 -12 -20 -25 -26 -21 -12 -1 9
*/

/*//#pragma GCC optimize("Ofast,unroll-loops")
//#pragma GCC target("sse4.2,abm,bmi,bmi2,popcnt,lzcnt,avx,avx2,fma")
#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
#include <iomanip>
#include <set>
#include <stack>
#include <map>
#include <list>
#include <string>
#include <cstring>
#include <cstdlib>
#include <cctype>
#include <fstream>
#include <ios>
#include <signal.h>
#include <queue>
#include <ctime>
#include <windows.h>
//#include "Header.h"
//#define f first
//#define s second

using namespace std;

int main(int argc, char* argv[]) {
    //SetConsoleCP(1251);
    //SetConsoleOutputCP(1251);
    //freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
    //string alf = "abcdefghijklmnopqrstuvwxyz";
    //string alf = "абвгдеёжзийклмнопрстуфхцчшщъыьэюя";
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    long long cnt = 0;
    for (long long i = 1; cnt + i <= 1e9; ) {
        cnt += i;
        i *= 2;
    }
    //cout << cnt << '\n';
    long long t = 1;
    cout << t << '\n';
    srand(time(0));
    while (t--) {
        cout << 100000 << '\n';
        for (long long i = 0; i < 1e5; ++i) {
            cout << 1000000 << ' ';
        }
        cout << '\n' << 100000 << '\n';
        for (long long i = 0; i < 1e5; ++i) {
            cout << 1 << ' ' << 1 << ' ' << 100000;
        }
    }
    return 0;
}

ll t, n, m, q, a, b, c, d, x, mx, mn, k, cnt, l, r, ans, temp, id;
string s, s1, s2;
bool flag = true;
cin >> t;
while (t--) {

}*/

Submission Info

Compile Error

Main.cpp: In function ‘int main(int, char**)’:
Main.cpp:86:18: warning: unused variable ‘eps’ [-Wunused-variable]
   86 |     const double eps = 0.000000001;
      |                  ^~~
Main.cpp:87:21: warning: unused variable ‘mod’ [-Wunused-variable]
   87 |     const long long mod = 998244353;
      |                     ^~~
Main.cpp:91:29: warning: unused variable ‘cnt1’ [-Wunused-variable]
   91 |     ll n, cur = 0, cnt = 0, cnt1 = 0, cnt2 = 0;
      |                             ^~~~
Main.cpp:91:39: warning: unused variable ‘cnt2’ [-Wunused-variable]
   91 |     ll n, cur = 0, cnt = 0, cnt1 = 0, cnt2 = 0;
      |                                       ^~~~
Main.cpp:95:10: warning: unused variable ‘flag’ [-Wunused-variable]
   95 |     bool flag = true;
      |          ^~~~
Main.cpp:77:14: warning: unused parameter ‘argc’ [-Wunused-parameter]
   77 | int main(int argc, char* argv[]) {
      |          ~~~~^~~~
Main.cpp:77:26: warning: unused parameter ‘argv’ [-Wunused-parameter]
   77 | int main(int argc, char* argv[]) {
      |                    ~~~~~~^~~~~~

Judge Result