oj.uz

답안 #404095

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
404095 2021-05-13T18:38:38 Z yoavL 코알라 (APIO17_koala) C++14
33 / 100
 1000 ms 324 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 = 8;

ll a[len], b[len];

ll qnum;

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)
{
    if ((i1 < 0) || (i2 < 0) || (i1 >= len) || (i2 >= len) || (i1 == i2)) while (true);
    //wpr(v);
    rep(i, 0, len) {
        a[i] = 0;
    }
    a[i1] = a[i2] = v;

    //pra();
    qnum++;
    //if (qnum > 2200) while (true);
    if (qnum > 700) while (true);
    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 false;
    
    //cout << "comp: " << i << ", " << j << endl;

    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) {
            return res;
        }
        if (res == 2) {
            low = mid + 1;
        }
        else {
            high = mid - 1;
        }
    }
    
    /*
    for (ll mid = 0; mid <= maxcap; mid++) {

        ll res = put_v_comp(mid, i, j);
        //wpr(res);
        if (res <= 1) {
            return res;
        }
        if (res == 2) {
            low = mid + 1;
        }
        else {
            high = mid - 1;
        }
    }
    */
    while (true);
    return false;
}

bool comp2(ll a, ll b)
{
    if (a == b) return false;
    ll tans = put_v_comp(100, a, b);
    if (tans > 1) while (true);
    return tans;
}
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.
    qnum = 0;
    return comp(0, 1);
}

void allValues(int N, int W, int* P) {
    qnum = 0;
    vll inds(len);

    for (ll i = 0; i < len; i++) {
        inds[i] = i;
    }
    //pr("wasup");
    if (W == 2 * N) {
        // TODO: Implement Subtask 4 solution here.
        // You may leave this block unmodified if you are not attempting this
        // subtask.
        sort(inds.begin(), inds.end(), comp2);
    }
    else {
        // TODO: Implement Subtask 5 solution here.
        // You may leave this block unmodified if you are not attempting this
        // subtask.
        

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

    }
    rep(i, 0, len)
    {
        P[i] = inds[i] + 1;
        if ((P[i] <= 0) || (P[i] > len)) while (true);
    }

}


/*


4 1
6 12
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 200
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 




4 1 
6 6 
5 3 2 1 6 4

4 1
100 200
100 1 99 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 98 97 


*/

Compilation message

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

Subtask #1
4.0 / 4.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 200 KB Output is correct
2 Correct 5 ms 200 KB Output is correct
3 Correct 5 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 312 KB Output is correct
2 Correct 19 ms 316 KB Output is correct
3 Correct 15 ms 200 KB Output is correct
4 Correct 15 ms 200 KB Output is correct

Subtask #3
14.0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Partially correct 72 ms 324 KB Output is partially correct
2 Partially correct 85 ms 316 KB Output is partially correct
3 Partially correct 78 ms 320 KB Output is partially correct
4 Partially correct 69 ms 320 KB Output is partially correct
5 Partially correct 71 ms 316 KB Output is partially correct
6 Partially correct 72 ms 320 KB Output is partially correct
7 Partially correct 70 ms 320 KB Output is partially correct
8 Partially correct 71 ms 312 KB Output is partially correct
9 Partially correct 72 ms 312 KB Output is partially correct
10 Partially correct 72 ms 320 KB Output is partially correct

Subtask #4
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 40 ms 200 KB Output is correct
2 Execution timed out 3060 ms 200 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #5
0 / 53.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 3054 ms 200 KB Time limit exceeded
2 Halted 0 ms 0 KB -