Submission #416354

#	Time	Username	Problem	Language	Result	Execution time	Memory
416354		model_code	Diamond Hands (innopolis2021_final_B)	C++17	100 / 100	96 ms	9296 KiB

Main

#include <cmath>
#include <functional>
#include <fstream>
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <set>
#include <map>
#include <list>
#include <time.h>
#include <math.h>
#include <random>
#include <deque>
#include <queue>
#include <cassert>
#include <unordered_map>
#include <unordered_set>
#include <iomanip>
#include <bitset>
#include <sstream>
#include <chrono>
#include <cstring>

using namespace std;

int const INF = 1e30;

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    int n;
    cin >> n;
    n++;
    vector<int> x(n, 0), y(n, 0);
    for (int i = 1; i < n; i++) {
        cin >> x[i] >> y[i];
    }
    for (int i = 1; i < n; i++) {
        if ((x[i] + y[i] + x[0] + y[0]) % 2 != 0) {
            cout << -1 << endl;
            return 0;
        }
        if (abs(y[i] - y[i - 1]) > x[i] - x[i - 1]) {
            cout << -1 << endl;
            return 0;
        }
    }
    vector<vector<int>> dp(2, vector<int>(n, INF));
    vector<vector<int>> pr(2, vector<int>(n));
    dp[0][0] = 1;
    dp[1][0] = 1;
    for (int i = 0; i < n - 1; i++) {
        for (int d = 0; d < 2; d++) {
            int dpVal = dp[d][i];
            if (y[i + 1] - y[i] == (x[i + 1] - x[i]) * (2 * d - 1) && dp[d][i + 1] > dpVal) {
                dp[d][i + 1] = dpVal;
                pr[d][i + 1] = d;
            }
            if (abs(y[i + 1] - y[i]) < (x[i + 1] - x[i]) && dp[d][i + 1] > dpVal + 2) {
                dp[d][i + 1] = dpVal + 2;
                pr[d][i + 1] = d;
            }
            if (dp[d ^ 1][i + 1] > dpVal + 1) {
                dp[d ^ 1][i + 1] = dpVal + 1;
                pr[d ^ 1][i + 1] = d;
            }
        }
    }
    vector<int> ansX, ansY;
    ansX.push_back(x[n - 1]);
    ansY.push_back(y[n - 1]);
    int d = dp[0][n - 1] < dp[1][n - 1] ? 0 : 1;
    for (int i = n - 1; i > 0; i--) {
        int prevD = pr[d][i];
        if (d == prevD) {
            if (y[i] - y[i - 1] == (x[i] - x[i - 1]) * (2 * d - 1)) {
                // skip point
            } else {
                // two intermediate points
                int delta = (y[i] - (y[i - 1] + (2 * prevD - 1) * (x[i] - x[i - 1]))) / -(2 * prevD - 1);
                assert(delta % 2 == 0 && delta >= 0);
                ansX.push_back(x[i - 1] + delta / 2);
                ansY.push_back(y[i - 1] - delta / 2 * (2 * d - 1));
                ansX.push_back(x[i - 1]);
                ansY.push_back(y[i - 1]);
            }
        } else {
            int delta = (y[i] - (y[i - 1] + (2 * prevD - 1) * (x[i] - x[i - 1]))) / -(2 * prevD - 1);
            assert(delta % 2 == 0 && delta >= 0);
            ansX.push_back(x[i] - delta / 2);
            ansY.push_back(y[i] - delta / 2 * (2 * d - 1));
        }
        d = prevD;
    }
    ansX.push_back(x[0]);
    ansY.push_back(y[0]);
    reverse(ansX.begin(), ansX.end());
    reverse(ansY.begin(), ansY.end());
    cout << ansX.size() - 1 << endl;
    for (int i = 0; i + 1 < ansX.size(); i++) {
        int l = ansX[i + 1] - ansX[i];
        char c = (ansY[i + 1] > ansY[i]) ? '+' : '-'; 
        cout << l << " " << c << "\n";
    }
    return 0;
}

Compilation message (stderr)

Main.cpp:27:17: warning: overflow in conversion from 'double' to 'int' changes value from '1.0e+30' to '2147483647' [-Woverflow]
   27 | int const INF = 1e30;
      |                 ^~~~
Main.cpp: In function 'int main()':
Main.cpp:101:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  101 |     for (int i = 0; i + 1 < ansX.size(); i++) {
      |                     ~~~~~~^~~~~~~~~~~~~

• Subtask 1: 6 / 6
• Subtask 2: 8 / 8
• Subtask 3: 10 / 10
• Subtask 4: 28 / 28
• Subtask 5: 17 / 17
• Subtask 6: 31 / 31