Submission #1299770

#	Time	Username	Problem	Language	Result	Execution time	Memory
1299770		Canuc80k	Rotating Lines (APIO25_rotate)	C++20	11 / 100	38 ms	3304 KiB

rotate

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

vector<array<int, 2>> a;
vector<int> pos;

long long cal(vector<int> v) {
    long long res = 0;
    for (int i = 0; i < (int) v.size(); i++){
        for (int j = i + 1; j < (int) v.size(); j++){
            int d = abs(v[i] - v[j]);
            res += std::min(d, 50000 - d);
        }
    }
    return res;
}

void rotate(std::vector<int> t, int x);
void energy(int n, std::vector<int> v) {
    pos.resize(n);
    for (int i = 0; i < v.size(); i ++) a.push_back({v[i], i});
    sort(a.begin(), a.end());
    for (int i = 0; i < v.size(); i ++) v[i] = a[i][0], pos[i] = a[i][1];
    vector<int> cur_vector = v;

    if (v.back() <= 25000) {
        for (int i = 0; i < v.size() / 2; i ++) 
            rotate({pos[i]}, 100000 - v[i]);
        for (int i = v.size() / 2; i < v.size(); i ++) 
            rotate({pos[i]}, 25000 - v[i]);
        return;
    } else {

        ll x = 49999 - 25000; ll old_value = cal(cur_vector);
        for (int g = 0; g < 100000; g ++) {
        for (auto x: cur_vector) cout << x << ' '; cout << endl;
        // cout << old_value << endl;
        if (old_value == n * 25000) {
            return;
        }
        if (cur_vector[0] >= x) break   ; 
        for (int i = v.size() - 1; i >= 0; i --) {
            for (int j = x + 25000; j >= v[i] + 1; j --) {
                ll o = cur_vector[i];
                cur_vector[i] = j;
                ll tmp = cal(cur_vector);
                // cout << "Debug: " << i << ' ' << o << ' ' << j << ' ' << old_value << ' ' << tmp << endl;
                if (tmp >= old_value) {
                    rotate({pos[i]}, j - o + 100000);
                    old_value = tmp;
                    // for (auto x: cur_vector) cout << x << ' '; cout << endl;
                    break;
                }
                cur_vector[i] = o;
            }
        }
        }
        v = cur_vector;
        a.clear(); 
        for (int i = 0; i < v.size(); i ++) a.push_back({v[i], pos[i]});
        sort(a.begin(), a.end());
        for (int i = 0; i < v.size(); i ++) v[i] = a[i][0], pos[i] = a[i][1];
        if (v[0] < x) cout << 1 / 0;
        // for (auto x: v) cout << x << ' '; cout << endl;
        // for (auto x: pos) cout << x << ' '; cout << endl; 
        for (int i = 0; i < v.size() / 2; i ++) 
            rotate({pos[i]}, x - v[i] + 100000);
        // cout << "??? " << endl;
        for (int i = v.size() / 2; i < v.size(); i ++) 
            rotate({pos[i]}, x + 25000 - v[i] + 100000);
        return;
    }
}

Compilation message (stderr)

rotate.cpp: In function 'void energy(int, std::vector<int>)':
rotate.cpp:64:33: warning: division by zero [-Wdiv-by-zero]
   64 |         if (v[0] < x) cout << 1 / 0;
      |                               ~~^~~

• Subtask 0: 0 / 0
• Subtask 1: 0 / 5
• Subtask 2: 11 / 11
• Subtask 3: 0 / 8
• Subtask 4: 0 / 15
• Subtask 5: 0 / 15
• Subtask 6: 0 / 20
• Subtask 7: 0 / 26