제출 #1299769

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1299769		Canuc80k	Rotating Lines (APIO25_rotate)	C++20	16 / 100	3095 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 ++) {
        if (cur_vector[0] >= x) break; 
        // for (auto x: cur_vector) cout << x << ' '; cout << endl;
        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;
    }
}

컴파일 시 표준 에러 (stderr) 메시지

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

• Subtask 0: 0 / 0
• Subtask 1: 5 / 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