oj.uz

Submission #208099

# Submission time Handle Problem Language Result Execution time Memory
208099 2020-03-10T02:55:00 Z ToMmyDong Coin Collecting (JOI19_ho_t4) C++11
8 / 100
 1000 ms 632 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
#define REP(i,n) for(int i=0;i<n;++i)
#define REP1(i,n) for(int i=1;i<=n;++i)
#define SZ(i) int(i.size())
#define eb emplace_back
#define ALL(i) i.begin(),i.end()
#define X first
#define Y second
#ifdef tmd
#define IOS()
#define debug(...) fprintf(stderr,"#%d: %s = ",__LINE__,#__VA_ARGS__),_do(__VA_ARGS__);
template<typename T> void _do(T &&x){cerr<<x<<endl;}
template<typename T, typename ...S> void _do(T &&x, S &&...y){cerr<<x<<", ";_do(y...);}
template<typename It> ostream& _printRng(ostream &os,It bg,It ed)
{
    os<<"{";
    for(It it=bg;it!=ed;it++) {
        os<<(it==bg?"":",")<<*it;
    }
    os<<"}";
    return os;
}
template<typename T> ostream &operator << (ostream &os,vector<T> &v){return _printRng(os,v.begin(), v.end());}
template<typename T> void pary(T bg, T ed){_printRng(cerr,bg,ed);cerr<<endl;}
#else
#define IOS() ios_base::sync_with_stdio(0);cin.tie(0);
#define endl '\n'
#define debug(...)
#define pary(...)
#endif

const int MAXN = 100005;
const ll MOD = 1000000007;

int n;
vector<pll> pos;

void solve (vector<int> x, ll &res) {
    sort(ALL(x));

    for (int i=1; i<=n; i++) {
        res += abs(x[i-1] - i);
    }
}

/*********************GoodLuck***********************/
int main () {
    IOS();

    cin >> n;

    vector<int> par;
    REP (i, n*2) {
        par.eb(i&1);
        int x, y;
        cin >> x >> y;
        pos.eb(x, y);
    }

    sort(ALL(par));

    ll ans = 0x3f3f3f3f3f3f3f3f;
    do {

        ll res = 0;
        vector<int> u, d;

        REP (i, n*2) {
            if (par[i]) {
                res += abs(pos[i].Y-1);
                u.eb(pos[i].X);
            } else {
                res += abs(pos[i].Y-2);
                d.eb(pos[i].X);
            }
        }

        solve(u,res);
        solve(d,res);

        ans = min(ans, res);


    } while (next_permutation(ALL(par)));

    cout << ans << endl;


}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 376 KB Output is correct
2 Correct 5 ms 376 KB Output is correct
3 Correct 5 ms 376 KB Output is correct
4 Correct 151 ms 376 KB Output is correct
5 Correct 138 ms 376 KB Output is correct
6 Correct 147 ms 376 KB Output is correct
7 Correct 156 ms 380 KB Output is correct
8 Correct 153 ms 380 KB Output is correct
9 Correct 151 ms 504 KB Output is correct
10 Correct 152 ms 384 KB Output is correct
11 Correct 133 ms 248 KB Output is correct
12 Correct 155 ms 504 KB Output is correct
13 Correct 144 ms 504 KB Output is correct
14 Correct 155 ms 504 KB Output is correct
15 Correct 148 ms 376 KB Output is correct
16 Correct 147 ms 376 KB Output is correct
17 Correct 154 ms 376 KB Output is correct
18 Correct 154 ms 376 KB Output is correct
19 Correct 146 ms 504 KB Output is correct
20 Correct 146 ms 504 KB Output is correct
21 Correct 147 ms 376 KB Output is correct
22 Correct 149 ms 376 KB Output is correct
23 Correct 155 ms 376 KB Output is correct
24 Correct 153 ms 248 KB Output is correct
25 Correct 149 ms 376 KB Output is correct
26 Correct 142 ms 376 KB Output is correct
27 Correct 144 ms 632 KB Output is correct
28 Correct 143 ms 376 KB Output is correct
29 Correct 148 ms 376 KB Output is correct
30 Correct 144 ms 376 KB Output is correct
31 Correct 153 ms 376 KB Output is correct
32 Correct 148 ms 300 KB Output is correct
33 Correct 145 ms 376 KB Output is correct

Subtask #2
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 376 KB Output is correct
2 Correct 5 ms 376 KB Output is correct
3 Correct 5 ms 376 KB Output is correct
4 Correct 151 ms 376 KB Output is correct
5 Correct 138 ms 376 KB Output is correct
6 Correct 147 ms 376 KB Output is correct
7 Correct 156 ms 380 KB Output is correct
8 Correct 153 ms 380 KB Output is correct
9 Correct 151 ms 504 KB Output is correct
10 Correct 152 ms 384 KB Output is correct
11 Correct 133 ms 248 KB Output is correct
12 Correct 155 ms 504 KB Output is correct
13 Correct 144 ms 504 KB Output is correct
14 Correct 155 ms 504 KB Output is correct
15 Correct 148 ms 376 KB Output is correct
16 Correct 147 ms 376 KB Output is correct
17 Correct 154 ms 376 KB Output is correct
18 Correct 154 ms 376 KB Output is correct
19 Correct 146 ms 504 KB Output is correct
20 Correct 146 ms 504 KB Output is correct
21 Correct 147 ms 376 KB Output is correct
22 Correct 149 ms 376 KB Output is correct
23 Correct 155 ms 376 KB Output is correct
24 Correct 153 ms 248 KB Output is correct
25 Correct 149 ms 376 KB Output is correct
26 Correct 142 ms 376 KB Output is correct
27 Correct 144 ms 632 KB Output is correct
28 Correct 143 ms 376 KB Output is correct
29 Correct 148 ms 376 KB Output is correct
30 Correct 144 ms 376 KB Output is correct
31 Correct 153 ms 376 KB Output is correct
32 Correct 148 ms 300 KB Output is correct
33 Correct 145 ms 376 KB Output is correct
34 Execution timed out 1077 ms 376 KB Time limit exceeded
35 Halted 0 ms 0 KB -

Subtask #3
0 / 63.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 376 KB Output is correct
2 Correct 5 ms 376 KB Output is correct
3 Correct 5 ms 376 KB Output is correct
4 Correct 151 ms 376 KB Output is correct
5 Correct 138 ms 376 KB Output is correct
6 Correct 147 ms 376 KB Output is correct
7 Correct 156 ms 380 KB Output is correct
8 Correct 153 ms 380 KB Output is correct
9 Correct 151 ms 504 KB Output is correct
10 Correct 152 ms 384 KB Output is correct
11 Correct 133 ms 248 KB Output is correct
12 Correct 155 ms 504 KB Output is correct
13 Correct 144 ms 504 KB Output is correct
14 Correct 155 ms 504 KB Output is correct
15 Correct 148 ms 376 KB Output is correct
16 Correct 147 ms 376 KB Output is correct
17 Correct 154 ms 376 KB Output is correct
18 Correct 154 ms 376 KB Output is correct
19 Correct 146 ms 504 KB Output is correct
20 Correct 146 ms 504 KB Output is correct
21 Correct 147 ms 376 KB Output is correct
22 Correct 149 ms 376 KB Output is correct
23 Correct 155 ms 376 KB Output is correct
24 Correct 153 ms 248 KB Output is correct
25 Correct 149 ms 376 KB Output is correct
26 Correct 142 ms 376 KB Output is correct
27 Correct 144 ms 632 KB Output is correct
28 Correct 143 ms 376 KB Output is correct
29 Correct 148 ms 376 KB Output is correct
30 Correct 144 ms 376 KB Output is correct
31 Correct 153 ms 376 KB Output is correct
32 Correct 148 ms 300 KB Output is correct
33 Correct 145 ms 376 KB Output is correct
34 Execution timed out 1077 ms 376 KB Time limit exceeded
35 Halted 0 ms 0 KB -