| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 127369 | ekrem | Scales (IOI15_scales) | C++98 | 699 ms | 508 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#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 (stderr)
| # | Verdict | Execution time | Memory | Grader output |
|---|---|---|---|---|
| Fetching results... | ||||