CSES - Datatähti 2025 alku - Results
Submission details
Task:Tikut
Sender:zli0122
Submission time:2024-11-10 23:04:42 +0200
Language:C++ (C++11)
Status:COMPILE ERROR

Compiler report

input/code.cpp: In function 'int main()':
input/code.cpp:73:14: error: conflicting declaration 'auto s'
   73 |         auto s = solve_maxmin(pieces, m, global_min);
      |              ^
input/code.cpp:70:14: note: previous declaration as 'std::pair<int, int> s'
   70 |         auto s = solve_minmax(pieces, m, global_min);
      |              ^
input/code.cpp:68:9: warning: unused variable 'max_index' [-Wunused-variable]
   68 |     int max_index, max_value, minmax, maxmin, d1, d2;
      |         ^~~~~~~~~
input/code.cpp:68:20: warning: unused variable 'max_value' [-Wunused-variable]
   68 |     int max_index, max_value, minmax, maxmin, d1, d2;
      |                    ^~~~~~~~~

Code

#include <bits/stdc++.h>
#define INF INT32_MAX/2 + 1;
using namespace std;
int N, M;
vector<int> S;
pair<int, int> solve_minmax(vector<int> pieces, vector<int> m, int global_min) {
// returns the index of the piece to cut, and returns the new difference
int minmax = 0;
int max_index, max_value;
for (int i = 0; i < N; i++) {
if (m[i] > m[minmax]) minmax = i;
}
// find max_value among the sticks after we minimize max.
max_index = (minmax == 0) ? 1 : 0;
max_value = (S[minmax]-1)/(pieces[minmax]+1) + 1;
for (int i = 0; i < N; i++) {
if (i == minmax) continue;
if (m[i] >= m[max_index] and m[i] > max_value) {
max_index = i;
max_value = m[max_index];
}
}
return {minmax, max_value - min(global_min, S[minmax]/(pieces[minmax]+1))};
}
pair<int, int> solve_maxmin(vector<int> pieces, vector<int> m, int global_min) {
// returns the index of the piece to cut, and returns the new difference
int maxmin = 0;
int max_index, max_value;
for (int i = 0; i < N; i++) {
if (m[i] > m[maxmin]) maxmin = i;
}
// find max_value among the sticks after we minimize max.
max_index = (maxmin == 0) ? 1 : 0;
max_value = (S[maxmin]-1)/(pieces[maxmin]+1) + 1;
for (int i = 0; i < N; i++) {
if (i == maxmin) continue;
if (m[i] >= m[max_index] and m[i] > max_value) {
max_index = i;
max_value = m[max_index];
}
}
return {maxmin, max_value - min(global_min, S[maxmin]/(pieces[maxmin]+1))};
}
int main() {
int N, M;
cin >> N >> M;
int a;
vector<int> pieces(N, 1);
vector<int> m(N);
for (int _ = 0; _ < N; _++) {
cin >> a;
S.push_back(a);
}
sort(S.rbegin(), S.rend());
int global_min = S.back();
for (int i = 0; i < N; i++) m[i]=S[i];
//for (auto i: s) cout << i << " ";cout << endl;
int max_index, max_value, minmax, maxmin, d1, d2;
for (int k = 1; k <= M; k++) {
auto s = solve_minmax(pieces, m, global_min);
minmax = s.first; d1 = s.second;
auto s = solve_maxmin(pieces, m, global_min);
maxmin = s.first; d2 = s.second;
if (d1 > d2) {
cout << d2 << " ";
minmax = maxmin;
} else cout << d1 << " ";
// cut the piece
pieces[minmax]++;
m[minmax] = (S[minmax]-1)/pieces[minmax] + 1;
global_min = min(global_min, S[minmax]/pieces[minmax]);
}
cout << "\n";
}