oj.uz

답안 #403840

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
403840 2021-05-13T13:57:51 Z yoavL 코알라 (APIO17_koala) C++14
33 / 100
 62 ms 328 KB 
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <set>
#include <unordered_set>
#include <map>
#include <unordered_map>
#include <queue>
#include <stack>
#include <bitset>
#include <math.h>
#include <fstream>
#include <iomanip>
#include "koala.h"

using namespace std;

using ll = int;
using ld = long double;
using vll = vector<ll>;
using vvll = vector<vll>;
using vvvll = vector<vvll>;
using vvvvll = vector<vvvll>;
using vb = vector<bool>;
using vvb = vector<vb>;
using vvvb = vector<vvb>;
using vld = vector<ld>;
using vstr = vector<string>;
using pll = pair<ll, ll>;
using vpll = vector<pll>;
using vvpll = vector<vpll>;
using pb = pair<bool, bool>;
using vpb = vector<pb>;
using vvpb = vector<vpb>;
using vi = vector<int>;
using vvi = vector<vi>;

const ll mod = (ll)1e9 + 7;
const ll inf = (ll)1e18;


#define F           first
#define S           second

#define FAST        ios_base::sync_with_stdio(0)
#define FASTIN		cin.tie(0)
#define FASTOUT		cout.tie(0)

#define upmin(a, b) a = min(a, b)
#define upmax(a, b) a = max(a, b)

#define whatvec(v) cout << #v << ": "; for(auto it = v.begin(); it != v.end(); ++it) cout << *it << " "; cout << endl;
#define prv(v) cout << #v << ": "; for(auto it = v.begin(); it != v.end(); ++it) cout << *it << " "; cout << endl;
#define wpr(x) cout << #x << " = " << (x) << endl;
#define wprv(v) cout << #v << ": "; for(auto it = v.begin(); it != v.end(); ++it) cout << *it << " "; cout << endl;
#define what(x) cout << #x << " = " << (x) << "\n";
#define pr(x) cout <<x << endl;

#define rep(i,s,e) for(ll i = s;i < e; i++)

#define all(x) x.begin(),x.end()
#define pb push_back


const ll len = 100;
const ll maxcap = 20;

ll a[len], b[len];

void fill(ll ind)
{
    for (ll i = 0; i < len; i++) a[i] = 0;
    a[ind] = 1;
}

void pra()
{
    pr("a:");
    rep(i, 0, len) {
        cout << a[i] << " ";
    }
    cout << endl;
}


void prb()
{
    pr("b:");
    rep(i, 0, len) {
        cout << b[i] << " ";
    }
    cout << endl;
}

int minValue(int N, int W) {
    //pr("here");
    // TODO: Implement Subtask 1 solution here.
    // You may leave this function unmodified if you are not attempting this
    // subtask.
    ll n = N, w = W;
    

    //vll a(n, 1);
    fill(0);
    rep(i, 0, len) b[i] = -1;
    bool ok = false;
    playRound(a, b);

    rep(i, 0, len) if (b[i] != -1) ok = true;
    if (!ok) while (true);
    for (ll i = 0; i < len; i++) {
        if (b[i] == 0) return i;
    }
    fill(1);
    playRound(a, b);
    rep(i, 0, len) {
        if (b[i] == 0) return i;
    }
    while (true);
    return 0;
}


int rec(vll ind)
{
    if (ind.size() == 1) {
        return ind[0];
    }
    ll sz = ind.size();
    ll cap = len / sz;
    rep(i, 0, len) {
        a[i] = 0;
    }
    rep(i, 0, sz) {
        a[ind[i]] = cap;
    }
    /*
    pr("a:");
    rep(i, 0, len) {
        cout << a[i] << " ";
    }
    cout << endl;
    */
    playRound(a, b);
    /*
    pr("b:");
    rep(i, 0, len) {
        cout << b[i] << " ";
    }
    cout << endl;
    */
    ll maxv = 0;
    rep(i, 0, len) {
        upmax(maxv, b[i]);
    }
    vll nind;
    rep(i, 0, len) {
        if (b[i] == maxv) nind.push_back(i);
    }
    return rec(nind);
}

int maxValue(int N, int W) {
    // TODO: Implement Subtask 2 solution here.
    // You may leave this function unmodified if you are not attempting this
    // subtask.


    vll ind;
    for (ll i = 0; i < len; i++) ind.push_back(i);
    return rec(ind);
}


int put_v_comp(ll v, ll i1, ll i2)
{
    //wpr(v);
    rep(i, 0, len) {
        a[i] = 0;
    }
    a[i1] = a[i2] = v;

    //pra();
    playRound(a, b);
    //prb();
    if (b[i1] > b[i2]) return 0;
    if (b[i1] < b[i2]) return 1;
    if (b[i1] > 0) return 2;
    return 3;
}






bool comp(ll i, ll j)
{
    
    if (i == j) return 0;
    bool change = 0;
    
    if (i > j) {
        change = 1;
        swap(i, j);
    }
    
    //cout << "comp: " << i << ", " << j << endl;
    
    //return false;
    ll low = 0, high = maxcap, mid = 0;
    while (low <= high) {
        mid = (low + high) / 2;

        ll res = put_v_comp(mid, i, j);
        //wpr(res);
        if (res <= 1) {
            bool tans = res;
            //cout << "returning: " << res << endl;
            if (change) return !tans;
            return tans;
        }
        if (res == 2) {
            low = mid + 1;
        }
        else {
            high = mid - 1;
        }
    }
    //while (true);
    return 0;
}


int greaterValue(int N, int W) {
    // TODO: Implement Subtask 3 solution here.
    // You may leave this function unmodified if you are not attempting this
    // subtask.

    return comp(0, 1);
}

void allValues(int N, int W, int* P) {
    //pr("wasup");
    if (W == 2 * N && false) {
        // TODO: Implement Subtask 4 solution here.
        // You may leave this block unmodified if you are not attempting this
        // subtask.
    }
    else {
        // TODO: Implement Subtask 5 solution here.
        // You may leave this block unmodified if you are not attempting this
        // subtask.
        //pr("hii");
        vll inds(len);
        for (ll i = 0; i < len; i++) {
            inds[i] = i;
        }

        sort(inds.begin(), inds.end(), comp);
        rep(i, 1, len) {
            if (comp(inds[i], inds[i - 1]) != 0) while (true);
        }
        rep(i, 0, len)
        {
            P[i] = inds[i]+1;
        }
        

    }
}


/*


4 1
6 6
5 3 2 1 6 4



3 1
6 6
5 3 2 1 6 4

3 1
6 6
3 5 2 1 6 4


4 1
6 6
5 3 2 1 6 4


4 1
6 6
5 3 2 1 6 4

3 1
6 6
1 2 5 3 6 4


3 1
6 6
5 4 3 2 1


4 1 
6 6 
5 3 2 1 6 4 

5 1
6 6
1 2 5 3 6 4


4 1
6 6
1 2 3 4 5 6


4 1
100 100
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 
39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 
74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100


4 1
100 100
100 99 98 97 96 95 94 93 92 91 90 89 88 87 86 85 84 83 82 81 80 79 78 77 76 75 74 73 72 71 70 69 68 67 66 
65 64 63 62 61 60 59 58 57 56 55 54 53 52 51 50 49 48 47 46 45 44 43 42 41 40 39 38 37 36 35 34 33 32 
31 30 29 28 27 26 25 24 23 22 21 20 19 18 17 16 15 14 13 12 11 10 9 8 7 6 5 4 3 2 1




4 1
100 100
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 
39 40 41 42 43 44 45 46 47 48 49 50 
100 99 98 97 96 95 94 93 92 91 90 89 88 87 86 85 84 83 82 81 80 79 78 77 76 75 74 73 72 71 70 69 68 67 66 
65 64 63 62 61 60 59 58 57 56 55 54 53 52 51 



*/

Compilation message

koala.cpp: In function 'int minValue(int, int)':
koala.cpp:102:8: warning: unused variable 'n' [-Wunused-variable]
  102 |     ll n = N, w = W;
      |        ^
koala.cpp:102:15: warning: unused variable 'w' [-Wunused-variable]
  102 |     ll n = N, w = W;
      |               ^

Subtask #1
4.0 / 4.0

# 결과 실행 시간 메모리 Grader output
1 Correct 6 ms 200 KB Output is correct
2 Correct 7 ms 200 KB Output is correct
3 Correct 6 ms 200 KB Output is correct
4 Correct 5 ms 200 KB Output is correct

Subtask #2
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 15 ms 200 KB Output is correct
2 Correct 15 ms 312 KB Output is correct
3 Correct 15 ms 312 KB Output is correct
4 Correct 15 ms 200 KB Output is correct

Subtask #3
14.0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 57 ms 328 KB Output is correct
2 Partially correct 62 ms 320 KB Output is partially correct
3 Correct 60 ms 316 KB Output is correct
4 Partially correct 58 ms 320 KB Output is partially correct
5 Partially correct 54 ms 328 KB Output is partially correct
6 Correct 54 ms 320 KB Output is correct
7 Correct 54 ms 320 KB Output is correct
8 Partially correct 56 ms 328 KB Output is partially correct
9 Partially correct 56 ms 312 KB Output is partially correct
10 Partially correct 58 ms 316 KB Output is partially correct

Subtask #4
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 47 ms 288 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 53.0

# 결과 실행 시간 메모리 Grader output
1 Partially correct 39 ms 200 KB Output is partially correct
2 Incorrect 46 ms 200 KB Output isn't correct
3 Halted 0 ms 0 KB -