| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 127369 |
2019-07-09T09:27:27 Z |
ekrem |
Scales (IOI15_scales) |
C++ |
|
699 ms |
508 KB |
#include "scales.h"
#include <bits/stdc++.h>
#define st first
#define nd second
#define mp make_pair
#define pb push_back
#define sol (k+k)
#define sag (k+k+1)
#define orta ((bas+son)/2)
#define coc g[node][i]
#define mod 1000000007
#define inf 1000000009
#define N 1005
using namespace std;
typedef long long ll;
typedef pair < int , int > ii;
typedef vector < int > vi;
int n, say, amk, u[N], uu[N];
vector < vi > a;
vi x, ans;
pair < ii , int > mx, kac;
void dfs(int ind){
if(ind == 6){
a.pb(x);
say++;
// if(rand()%100 == 0)for(int i = 1; i <= 6; i++)cout << x[i] << " ";cout << endl;
return;
}
for(int i = 1; i <= 6; i++)
if(!uu[i]){
uu[i]++;
x.pb(i);
dfs(ind + 1);
x.pop_back();
uu[i]--;
}
}
int getL(int i, int bir, int iki, int uc, int ans, int d){
if(a[i][bir] >= a[i][ans] and a[i][iki] >= a[i][ans] and a[i][uc] >= a[i][ans])
return 0;
u[i] += d;
return 1;
}
int getH(int i, int bir, int iki, int uc, int ans, int d){
if(a[i][bir] <= a[i][ans] and a[i][iki] <= a[i][ans] and a[i][uc] <= a[i][ans])
return 0;
u[i] += d;
return 1;
}
int getM(int i, int bir, int iki, int uc, int ans, int d){
int buy = 0, kuc = 0;
if(a[i][bir] <= a[i][ans])
kuc++;
else
buy++;
if(a[i][iki] <= a[i][ans])
kuc++;
else
buy++;
if(a[i][uc] <= a[i][ans])
kuc++;
else
buy++;
if(kuc == 2 and buy == 1)
return 0;
u[i] += d;
return 1;
}
int getN(int i, int bir, int iki, int uc, int dor, int ans, int d){
ii mn = mp(inf, inf);
if(a[i][bir] > a[i][dor])mn = min(mn, mp(a[i][bir], bir));
if(a[i][iki] > a[i][dor])mn = min(mn, mp(a[i][iki], iki));
if(a[i][uc] > a[i][dor])mn = min(mn, mp(a[i][uc], uc));
if(mn.st == inf){
mn = min(mn, mp(a[i][bir], bir));
mn = min(mn, mp(a[i][iki], iki));
mn = min(mn, mp(a[i][uc], uc));
}
if(mn.nd == ans)
return 0;
u[i] += d;
return 1;
}
int sorr(int bir, int iki, int uc, int dor, int ans, int d){
int say = 0;
for(int i = 1; i <= 720; i++){
if(u[i])
continue;
// if(bir == 1 and iki == 2 and uc == 3 and dor == -1)
// cout << ans << " " << say << " " << d << endl;
if(dor == -2)
say += getL(i, bir, iki, uc, ans, d);
else if(dor == -1)
say += getM(i, bir, iki, uc, ans, d);
else if(dor == 0)
say += getH(i, bir, iki, uc, ans, d);
else
say += getN(i, bir, iki, uc, dor, ans, d);
}
return say;
}
void sor(int ind){
if(ind == 3){
for(int i = -2; i <= 6; i++)
if(!uu[i]){
x.pb(i);
kac.st.st = sorr(x[1], x[2], x[3], x[4], x[1], 0);
kac.st.nd = sorr(x[1], x[2], x[3], x[4], x[2], 0);
kac.nd = sorr(x[1], x[2], x[3], x[4], x[3], 0);
if(kac.nd < kac.st.nd)
swap(kac.nd, kac.st.nd);
if(kac.st.nd < kac.st.st)
swap(kac.st.nd, kac.st.st);
if(kac.nd < kac.st.nd)
swap(kac.nd, kac.st.nd);
if(kac > mx){
mx = kac;
ans = x;
}
x.pop_back();
}
return;
}
for(int i = 1; i <= 6; i++)
if(!uu[i]){
uu[i]++;
x.pb(i);
sor(ind + 1);
x.pop_back();
uu[i]--;
}
}
void init(int T){
}
void orderCoins(){
a.clear();x.clear();ans.clear();
memset(u, 0, sizeof u);
memset(uu, 0, sizeof uu);
say = 0;
x.pb(0);
a.pb(x);
dfs(0);
// cout << a.size() << endl;
int W[] = {1, 2, 3, 4, 5, 6};
// cout << getLightest(1, 2, 3) << endl;
// cout << getHeaviest(1, 2, 3) << endl;
// cout << getMedian(1, 2, 3) << endl;
while(say > 1){
// cout << say << endl;
// amk++;if(amk >= 100)assert(0);
mx = mp(mp(-1, -1), -1);
sor(0);
// cout << mx << endl;
// cout << ans[1] << " " << ans[2] << " " << ans[3] << " " << ans[4] << " -> ";
int cvp = 0;
if(ans[4] == -2)
cvp = getLightest(ans[1], ans[2], ans[3]);
else if(ans[4] == -1)
cvp = getMedian(ans[1], ans[2], ans[3]);
else if(ans[4] == 0)
cvp = getHeaviest(ans[1], ans[2], ans[3]);
else
cvp = getNextLightest(ans[1], ans[2], ans[3], ans[4]);
say -= sorr(ans[1], ans[2], ans[3], ans[4], cvp, 1);
// if(say == 2){
// // for(int i = 1; i <= 720; i++){
// // if(u[i])continue;
// // cout << "GEL -> ";
// // for(int j = 1; j <= 6; j++)
// // cout << a[i][j] << " ";
// // cout << endl;
// // }
// // exit(0);
// }
// cout << cvp << endl;
}
for(int i = 1; i <= 720; i++){
if(u[i])continue;
for(int j = 1; j <= 6; j++)
W[a[i][j] - 1] = j;
}
// cout << say << endl;
answer(W);
}
Compilation message
scales.cpp: In function 'int getL(int, int, int, int, int, int)':
scales.cpp:42:57: warning: declaration of 'ans' shadows a global declaration [-Wshadow]
int getL(int i, int bir, int iki, int uc, int ans, int d){
^
scales.cpp:22:7: note: shadowed declaration is here
vi x, ans;
^~~
scales.cpp: In function 'int getH(int, int, int, int, int, int)':
scales.cpp:49:57: warning: declaration of 'ans' shadows a global declaration [-Wshadow]
int getH(int i, int bir, int iki, int uc, int ans, int d){
^
scales.cpp:22:7: note: shadowed declaration is here
vi x, ans;
^~~
scales.cpp: In function 'int getM(int, int, int, int, int, int)':
scales.cpp:56:57: warning: declaration of 'ans' shadows a global declaration [-Wshadow]
int getM(int i, int bir, int iki, int uc, int ans, int d){
^
scales.cpp:22:7: note: shadowed declaration is here
vi x, ans;
^~~
scales.cpp: In function 'int getN(int, int, int, int, int, int, int)':
scales.cpp:76:66: warning: declaration of 'ans' shadows a global declaration [-Wshadow]
int getN(int i, int bir, int iki, int uc, int dor, int ans, int d){
^
scales.cpp:22:7: note: shadowed declaration is here
vi x, ans;
^~~
scales.cpp: In function 'int sorr(int, int, int, int, int, int)':
scales.cpp:92:59: warning: declaration of 'ans' shadows a global declaration [-Wshadow]
int sorr(int bir, int iki, int uc, int dor, int ans, int d){
^
scales.cpp:22:7: note: shadowed declaration is here
vi x, ans;
^~~
scales.cpp:93:6: warning: declaration of 'say' shadows a global declaration [-Wshadow]
int say = 0;
^~~
scales.cpp:20:8: note: shadowed declaration is here
int n, say, amk, u[N], uu[N];
^~~
scales.cpp: In function 'void init(int)':
scales.cpp:145:15: warning: unused parameter 'T' [-Wunused-parameter]
void init(int T){
^
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Partially correct |
624 ms |
424 KB |
Output is partially correct |
| 2 |
Correct |
619 ms |
420 KB |
Output is correct |
| 3 |
Partially correct |
615 ms |
436 KB |
Output is partially correct |
| 4 |
Partially correct |
617 ms |
436 KB |
Output is partially correct |
| 5 |
Partially correct |
617 ms |
420 KB |
Output is partially correct |
| 6 |
Partially correct |
615 ms |
428 KB |
Output is partially correct |
| 7 |
Partially correct |
618 ms |
424 KB |
Output is partially correct |
| 8 |
Partially correct |
615 ms |
428 KB |
Output is partially correct |
| 9 |
Correct |
616 ms |
376 KB |
Output is correct |
| 10 |
Correct |
613 ms |
504 KB |
Output is correct |
| 11 |
Correct |
609 ms |
476 KB |
Output is correct |
| 12 |
Partially correct |
614 ms |
376 KB |
Output is partially correct |
| 13 |
Partially correct |
613 ms |
376 KB |
Output is partially correct |
| 14 |
Partially correct |
618 ms |
376 KB |
Output is partially correct |
| 15 |
Correct |
612 ms |
476 KB |
Output is correct |
| 16 |
Partially correct |
618 ms |
476 KB |
Output is partially correct |
| 17 |
Correct |
616 ms |
424 KB |
Output is correct |
| 18 |
Correct |
615 ms |
508 KB |
Output is correct |
| 19 |
Correct |
614 ms |
508 KB |
Output is correct |
| 20 |
Partially correct |
616 ms |
476 KB |
Output is partially correct |
| 21 |
Partially correct |
617 ms |
504 KB |
Output is partially correct |
| 22 |
Partially correct |
623 ms |
504 KB |
Output is partially correct |
| 23 |
Partially correct |
620 ms |
420 KB |
Output is partially correct |
| 24 |
Partially correct |
614 ms |
504 KB |
Output is partially correct |
| 25 |
Correct |
610 ms |
376 KB |
Output is correct |
| 26 |
Partially correct |
622 ms |
380 KB |
Output is partially correct |
| 27 |
Partially correct |
621 ms |
504 KB |
Output is partially correct |
| 28 |
Partially correct |
623 ms |
376 KB |
Output is partially correct |
| 29 |
Partially correct |
627 ms |
504 KB |
Output is partially correct |
| 30 |
Partially correct |
614 ms |
476 KB |
Output is partially correct |
| 31 |
Correct |
699 ms |
420 KB |
Output is correct |
| 32 |
Partially correct |
609 ms |
504 KB |
Output is partially correct |
| 33 |
Correct |
617 ms |
376 KB |
Output is correct |
| 34 |
Partially correct |
609 ms |
504 KB |
Output is partially correct |
| 35 |
Partially correct |
610 ms |
504 KB |
Output is partially correct |
| 36 |
Partially correct |
616 ms |
504 KB |
Output is partially correct |
| 37 |
Partially correct |
618 ms |
504 KB |
Output is partially correct |
| 38 |
Correct |
610 ms |
504 KB |
Output is correct |
| 39 |
Partially correct |
617 ms |
504 KB |
Output is partially correct |
| 40 |
Partially correct |
616 ms |
476 KB |
Output is partially correct |
