| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 286308 |
2020-08-30T09:46:03 Z |
abyyskit |
Scales (IOI15_scales) |
C++14 |
|
319 ms |
664 KB |
#include "scales.h"
#include<bits/stdc++.h>
using namespace std;
#define FOR(i, x, y) for(int i = x; i < y; ++i)
#define pb push_back
vector<vector<int>> UNI;
vector<vector<int>> Q;
void init(int T) {
// cout << "starting preprocessing\n";
vector<int> tmp = {1, 2, 3, 4, 5, 6};
UNI.pb(tmp);
while(next_permutation(tmp.begin(), tmp.end())){
UNI.pb(tmp);
}
FOR(i, 1, 7){
FOR(j, i + 1, 7){
FOR(k, j + 1, 7){
FOR(ii, 0, 3){
Q.pb({i, j, k, ii});
Q.pb({i, k, j, ii});
Q.pb({j, i, k, ii});
Q.pb({j, k, i, ii});
Q.pb({k, j, i, ii});
Q.pb({k, i, j, ii});
}
}
}
}
set<vector<int>> s;
FOR(i, 0, UNI.size()){
vector<int> TMP = {UNI[i][0], UNI[i][1], UNI[i][2], UNI[i][3], 0};
if (s.count(TMP) == 0){
s.insert(TMP);
Q.pb(TMP);
}
}
// cout << "preprocessed\n";
return;
}
int qans(vector<int>& q, vector<int>& pos){
if (q.size() == 4){
if (q.back() == 0){
//smallest
FOR(i, 0, pos.size()){
FOR(j, 0, 3){
if (pos[i] == q[j]){
return q[j];
}
}
}
}
else if (q.back() == 2){
//largest
FOR(i, 0, pos.size()){
FOR(j, 0, 3){
if (pos[5 - i] == q[j]){
return q[j];
}
}
}
}
else{
//median
bool flag = false;
FOR(i, 0, pos.size()){
FOR(j, 0, 3){
if (pos[i] == q[j]){
if (flag){
return q[j];
}
else{
flag = true;
}
}
}
}
}
}
//4 coins on scale
int small = -1;
bool flag = false;
FOR(i, 0, pos.size()){
FOR(j, 0, 3){
if (pos[i] == q[j]){
if (small == -1){
small = q[j];
}
if (flag){
return q[j];
}
}
}
if (pos[i] == q[3]){
flag = true;
}
}
return small;
}
pair<int, long double> value(vector<int>& q, vector<vector<int>>& uni){
vector<int> dist(6);
FOR(i, 0, uni.size()){
dist[qans(q, uni[i]) - 1]++;
}
int ans = 0;
long double ans2 = 0;
FOR(i, 0, dist.size()){
ans2 += dist[i]*dist[i];
if (dist[i] > ans){
ans = dist[i];
}
}
ans2 = sqrt(ans2/3);
return {ans, ans2};
}
void orderCoins() {
/* ... */
int C = 0;
vector<vector<int>> uni = UNI;
// cout << Q.size() << "\n";
// vector<int> test = {3, 4, 6, 2, 1, 5};
while(uni.size() > 1){
// cout << C << "\n";
C++;
vector<pair<int, long double>> qv(Q.size());
FOR(i, 0, Q.size()){
qv[i] = value(Q[i], uni);
}
// cout << "values calculated\n";
int ind = 0;
pair<int, long double> ans = qv[0];
FOR(i, 0, qv.size()){
if (qv[i].first < ans.first){
ans = qv[i];
ind = i;
}
if (qv[i].first == ans.first){
if (qv[i].second < ans.second){
ans = qv[i];
ind = i;
}
}
}
// if (uni.size() == 720){
// ind = 669;
// }
// cout << ans.first << " " << ans.second << "\n";
int A;
if (Q[ind].size() == 4){
if (Q[ind].back() == 0){
A = getLightest(Q[ind][0], Q[ind][1], Q[ind][2]);
}
else if (Q[ind].back() == 2){
A = getHeaviest(Q[ind][0], Q[ind][1], Q[ind][2]);
}
else{
A = getMedian(Q[ind][0], Q[ind][1], Q[ind][2]);
}
}
else{
A = getNextLightest(Q[ind][0], Q[ind][1], Q[ind][2], Q[ind][3]);
}
// cout << "A = " << A << "\n";
vector<vector<int>> Nuni;
FOR(i, 0, uni.size()){
if (qans(Q[ind], uni[i]) == A){
Nuni.pb(uni[i]);
}
}
swap(Nuni, uni);
/* cout << "uni: " << uni.size() << "\n";
FOR(i, 0, Q[ind].size()){
cout << Q[ind][i] << " ";
}
cout << "\n";
cout << qans(Q[ind], test) << "\n";
cout << "end\n";*/
}
//cout << "Done\n";
int W[] = {uni[0][0], uni[0][1], uni[0][2], uni[0][3], uni[0][4], uni[0][5]};
/* cout << "Answer is: ";
FOR(i, 0, 6){
cout << W[i] << " ";
}
cout << "\n";*/
answer(W);
return;
}
Compilation message
scales.cpp: In function 'void init(int)':
scales.cpp:4:39: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
4 | #define FOR(i, x, y) for(int i = x; i < y; ++i)
......
33 | FOR(i, 0, UNI.size()){
| ~~~~~~~~~~~~~~~~
scales.cpp:33:2: note: in expansion of macro 'FOR'
33 | FOR(i, 0, UNI.size()){
| ^~~
scales.cpp:11:15: warning: unused parameter 'T' [-Wunused-parameter]
11 | void init(int T) {
| ~~~~^
scales.cpp: In function 'int qans(std::vector<int>&, std::vector<int>&)':
scales.cpp:4:39: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
4 | #define FOR(i, x, y) for(int i = x; i < y; ++i)
......
48 | FOR(i, 0, pos.size()){
| ~~~~~~~~~~~~~~~~
scales.cpp:48:4: note: in expansion of macro 'FOR'
48 | FOR(i, 0, pos.size()){
| ^~~
scales.cpp:4:39: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
4 | #define FOR(i, x, y) for(int i = x; i < y; ++i)
......
58 | FOR(i, 0, pos.size()){
| ~~~~~~~~~~~~~~~~
scales.cpp:58:4: note: in expansion of macro 'FOR'
58 | FOR(i, 0, pos.size()){
| ^~~
scales.cpp:4:39: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
4 | #define FOR(i, x, y) for(int i = x; i < y; ++i)
......
69 | FOR(i, 0, pos.size()){
| ~~~~~~~~~~~~~~~~
scales.cpp:69:4: note: in expansion of macro 'FOR'
69 | FOR(i, 0, pos.size()){
| ^~~
scales.cpp:4:39: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
4 | #define FOR(i, x, y) for(int i = x; i < y; ++i)
......
86 | FOR(i, 0, pos.size()){
| ~~~~~~~~~~~~~~~~
scales.cpp:86:2: note: in expansion of macro 'FOR'
86 | FOR(i, 0, pos.size()){
| ^~~
scales.cpp: In function 'std::pair<int, long double> value(std::vector<int>&, std::vector<std::vector<int> >&)':
scales.cpp:4:39: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
4 | #define FOR(i, x, y) for(int i = x; i < y; ++i)
......
107 | FOR(i, 0, uni.size()){
| ~~~~~~~~~~~~~~~~
scales.cpp:107:2: note: in expansion of macro 'FOR'
107 | FOR(i, 0, uni.size()){
| ^~~
scales.cpp:4:39: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
4 | #define FOR(i, x, y) for(int i = x; i < y; ++i)
......
112 | FOR(i, 0, dist.size()){
| ~~~~~~~~~~~~~~~~~
scales.cpp:112:2: note: in expansion of macro 'FOR'
112 | FOR(i, 0, dist.size()){
| ^~~
scales.cpp: In function 'void orderCoins()':
scales.cpp:4:39: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
4 | #define FOR(i, x, y) for(int i = x; i < y; ++i)
......
132 | FOR(i, 0, Q.size()){
| ~~~~~~~~~~~~~~
scales.cpp:132:3: note: in expansion of macro 'FOR'
132 | FOR(i, 0, Q.size()){
| ^~~
scales.cpp:4:39: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, long double> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
4 | #define FOR(i, x, y) for(int i = x; i < y; ++i)
......
138 | FOR(i, 0, qv.size()){
| ~~~~~~~~~~~~~~~
scales.cpp:138:3: note: in expansion of macro 'FOR'
138 | FOR(i, 0, qv.size()){
| ^~~
scales.cpp:4:39: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
4 | #define FOR(i, x, y) for(int i = x; i < y; ++i)
......
171 | FOR(i, 0, uni.size()){
| ~~~~~~~~~~~~~~~~
scales.cpp:171:3: note: in expansion of macro 'FOR'
171 | FOR(i, 0, uni.size()){
| ^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Partially correct |
291 ms |
512 KB |
Output is partially correct |
| 2 |
Partially correct |
290 ms |
632 KB |
Output is partially correct |
| 3 |
Partially correct |
291 ms |
512 KB |
Output is partially correct |
| 4 |
Correct |
286 ms |
512 KB |
Output is correct |
| 5 |
Partially correct |
291 ms |
536 KB |
Output is partially correct |
| 6 |
Partially correct |
292 ms |
632 KB |
Output is partially correct |
| 7 |
Partially correct |
290 ms |
632 KB |
Output is partially correct |
| 8 |
Partially correct |
292 ms |
632 KB |
Output is partially correct |
| 9 |
Partially correct |
286 ms |
512 KB |
Output is partially correct |
| 10 |
Partially correct |
292 ms |
632 KB |
Output is partially correct |
| 11 |
Partially correct |
288 ms |
532 KB |
Output is partially correct |
| 12 |
Partially correct |
292 ms |
512 KB |
Output is partially correct |
| 13 |
Partially correct |
288 ms |
512 KB |
Output is partially correct |
| 14 |
Partially correct |
295 ms |
512 KB |
Output is partially correct |
| 15 |
Partially correct |
286 ms |
512 KB |
Output is partially correct |
| 16 |
Partially correct |
288 ms |
632 KB |
Output is partially correct |
| 17 |
Partially correct |
289 ms |
512 KB |
Output is partially correct |
| 18 |
Partially correct |
288 ms |
512 KB |
Output is partially correct |
| 19 |
Partially correct |
293 ms |
512 KB |
Output is partially correct |
| 20 |
Partially correct |
291 ms |
536 KB |
Output is partially correct |
| 21 |
Partially correct |
287 ms |
512 KB |
Output is partially correct |
| 22 |
Partially correct |
286 ms |
632 KB |
Output is partially correct |
| 23 |
Partially correct |
287 ms |
512 KB |
Output is partially correct |
| 24 |
Partially correct |
292 ms |
512 KB |
Output is partially correct |
| 25 |
Partially correct |
288 ms |
632 KB |
Output is partially correct |
| 26 |
Correct |
290 ms |
512 KB |
Output is correct |
| 27 |
Partially correct |
291 ms |
664 KB |
Output is partially correct |
| 28 |
Partially correct |
290 ms |
536 KB |
Output is partially correct |
| 29 |
Partially correct |
290 ms |
632 KB |
Output is partially correct |
| 30 |
Partially correct |
289 ms |
512 KB |
Output is partially correct |
| 31 |
Partially correct |
294 ms |
512 KB |
Output is partially correct |
| 32 |
Partially correct |
291 ms |
636 KB |
Output is partially correct |
| 33 |
Correct |
319 ms |
632 KB |
Output is correct |
| 34 |
Partially correct |
319 ms |
632 KB |
Output is partially correct |
| 35 |
Partially correct |
294 ms |
512 KB |
Output is partially correct |
| 36 |
Partially correct |
290 ms |
512 KB |
Output is partially correct |
| 37 |
Correct |
304 ms |
512 KB |
Output is correct |
| 38 |
Partially correct |
295 ms |
512 KB |
Output is partially correct |
| 39 |
Partially correct |
292 ms |
636 KB |
Output is partially correct |
| 40 |
Partially correct |
298 ms |
540 KB |
Output is partially correct |
