제출 #744324

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
744324		becaido	코알라 (APIO17_koala)	C++17	76 / 100	54 ms	340 KiB

koala

#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx,popcnt,sse4,abm")
#include <bits/stdc++.h>
using namespace std;

#ifndef WAIMAI
#include "koala.h"
#endif // WAIMAI

#ifdef WAIMAI
#define debug(HEHE...) cout << "[" << #HEHE << "] : ", dout(HEHE)
void dout() {cout << '\n';}
template<typename T, typename...U>
void dout(T t, U...u) {cout << t << (sizeof...(u) ? ", " : ""), dout(u...);}
#else
#define debug(...) 7122
#endif

#define ll long long
#define Waimai ios::sync_with_stdio(false), cin.tie(0)
#define FOR(x,a,b) for (int x = a, I = b; x <= I; x++)
#define pb emplace_back
#define F first
#define S second

#ifdef WAIMAI
void playRound(int *B, int *R);
#endif // WAIMAI

const int SIZE = 105;

int a[SIZE], b[SIZE];

int minValue(int N, int W) {
    a[0] = 1;
    fill(a + 1, a + N, 0);
    playRound(a, b);
    FOR (i, 0, N - 1) if (b[i] == 0) return i;
}

int maxValue(int N, int W) {
    vector<int> big(N);
    iota(big.begin(), big.end(), 0);
    while (big.size() > 1) {
        int w = W / big.size();
        fill(a, a + N, 0);
        for (int p : big) a[p] = w;
        playRound(a, b);
        vector<int> tmp;
        for (int p : big) if (b[p] > a[p]) tmp.pb(p);
        big = tmp;
    }
    if (big.size() == 0) return -1;
    return big[0];
}

int greaterValue(int N, int W, int p1, int p2) {
    if (W == 2 * N) {
        fill(a, a + N, 0);
        a[p1] = a[p2] = N;
        playRound(a, b);
        return b[p1] > a[p1] ? p1 : p2;
    }
    int l = 1, r = W / 8;
    while (l < r) {
        int mid = (l + r) / 2;
        fill(a, a + N, 0);
        a[p1] = a[p2] = mid;
        playRound(a, b);
        bool big1 = b[p1] > a[p1], big2 = b[p2] > a[p2];
        if (big1 && big2) l = mid + 1;
        else if (!big1 && !big2) r = mid - 1;
        else return big1 ? p1 : p2;
    }
}
int greaterValue(int N, int W) {
    return greaterValue(N, W, 0, 1);
}

void allValues(int N, int W, int *P) {
    vector<int> pos(N);
    iota(pos.begin(), pos.end(), 0);
    auto divide = [&](auto divide, vector<int> &pos)->void {
        if (pos.size() <= 1) return;
        int mid = pos.size() / 2;
        vector<int> pl, pr;
        FOR (i, 0, mid - 1) pl.pb(pos[i]);
        FOR (i, mid, pos.size() - 1) pr.pb(pos[i]);
        pos.clear();
        divide(divide, pl);
        divide(divide, pr);
        for (int il = 0, ir = 0; il < pl.size() || ir < pr.size();) {
            if (ir == pr.size() || (il < pl.size() && greaterValue(N, W, pl[il], pr[ir]) == pr[ir])) pos.pb(pl[il++]);
            else pos.pb(pr[ir++]);
        }
        pl.clear(), pr.clear();
    };
    divide(divide, pos);
    FOR (i, 0, N - 1) P[pos[i]] = i + 1;
}

/*
4 1
100 100 1
in1
1 1
6 6 5 3 2 1 6 4
out1
3
in2
2 1
6 6 5 3 2 1 6 4
out2
4
in3
3 1
6 6
5 3 2 1 6 4
out3
0
in4
4 1
6 12 5 3 2 1 6 4
in5
4 1
6 6 5 3 2 1 6 4
*/

#ifdef WAIMAI
static int N, W;
static int P[105];

static int maxQueries = 3200;
static int numQueries;

static void runGame(int F);
static void grader();

int main() {
    grader();
    return 0;
}

void playRound(int *B, int *R) {
    int i, j;

    int S = 0;
    for (i=0;i<N;++i) {
        if ( !(B[i] >= 0 && B[i] <= W) ) {
            printf("Invalid query.\n");
            exit(0);
        }
        S += B[i];
    }
    if (S > W) {
        printf("Invalid query.\n");
        exit(0);
    }

    numQueries++;
    if (numQueries > maxQueries) {
        printf("Too many queries.\n");
        exit(0);
    }

    int cache[2][205];
    int num[2][205];
    char taken[105][205];

    for (i=0;i<205;++i) {
        cache[1][i] = 0;
        num[1][i] = 0;
    }

    for (i=0;i<N;++i) {
        int v = B[i]+1;
        int ii = i&1;
        int o = ii^1;
        for (j=0;j<=W;++j) {
            cache[ii][j] = cache[o][j];
            num[ii][j] = num[o][j];
            taken[i][j] = 0;
        }
        for (j=W;j>=v;--j) {
            int h = cache[o][j-v] + P[i];
            int hn = num[o][j-v] + 1;
            if (h > cache[ii][j] || (h == cache[ii][j] && hn > num[ii][j])) {
                cache[ii][j] = h;
                num[ii][j] = hn;
                taken[i][j] = 1;
            } else {
                taken[i][j] = 0;
            }
        }
    }

    int cur = W;
    for (i=N-1;i>=0;--i) {
        R[i] = taken[i][cur] ? (B[i] + 1) : 0;
        cur -= R[i];
    }
}

int maxq;
mt19937 rng(time(NULL));
static void runGame(int F) {
    int i;

    scanf("%d %d",&N,&W);
    //N = W = 100;

    //printf("random?\n");
    int x = 1;
    //scanf("%d", &x);
    if (x == 1) {
        printf("random array = ");
        iota(P, P + N, 1);
        shuffle(P, P + N, rng);
        for (int i = 0; i < N; i++) printf("%d ", P[i]);
        printf("\n");
    } else {
        for (i=0;i<N;++i) {
            scanf("%d",&P[i]);
        }
    }

    numQueries = 0;
    if (F == 1) {
        printf("%d\n", minValue(N, W));
    } else if (F == 2) {
        printf("%d\n", maxValue(N, W));
    } else if (F == 3) {
        printf("%d\n", greaterValue(N, W));
    } else if (F == 4) {
        int userP[105];
        allValues(N, W, userP);
        for (i=0;i<N;i++) printf("%d ",userP[i]);
        printf("\n");
    }
    printf("Made %d calls to playRound.\n", numQueries);
    maxq = max(maxq, numQueries);
}

static void grader() {
    int i;

    int F, G;
    scanf("%d %d",&F,&G);

    for (i=0;i<G;i++) {
        runGame(F);
    }
    printf("maxQ = %d\n", maxq);
}
#endif // WAIMAI

컴파일 시 표준 에러 (stderr) 메시지

koala.cpp: In lambda function:
koala.cpp:92:37: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   92 |         for (int il = 0, ir = 0; il < pl.size() || ir < pr.size();) {
      |                                  ~~~^~~~~~~~~~~
koala.cpp:92:55: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   92 |         for (int il = 0, ir = 0; il < pl.size() || ir < pr.size();) {
      |                                                    ~~~^~~~~~~~~~~
koala.cpp: In instantiation of 'allValues(int, int, int*)::<lambda(auto:23, std::vector<int>&)> [with auto:23 = allValues(int, int, int*)::<lambda(auto:23, std::vector<int>&)>]':
koala.cpp:98:23:   required from here
koala.cpp:92:37: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   92 |         for (int il = 0, ir = 0; il < pl.size() || ir < pr.size();) {
      |                                  ~~~^~~~~~~~~~~
koala.cpp:92:55: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   92 |         for (int il = 0, ir = 0; il < pl.size() || ir < pr.size();) {
      |                                                    ~~~^~~~~~~~~~~
koala.cpp:93:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   93 |             if (ir == pr.size() || (il < pl.size() && greaterValue(N, W, pl[il], pr[ir]) == pr[ir])) pos.pb(pl[il++]);
      |                 ~~~^~~~~~~~~~~~
koala.cpp:93:40: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   93 |             if (ir == pr.size() || (il < pl.size() && greaterValue(N, W, pl[il], pr[ir]) == pr[ir])) pos.pb(pl[il++]);
      |                                     ~~~^~~~~~~~~~~
koala.cpp: In function 'int minValue(int, int)':
koala.cpp:39:1: warning: control reaches end of non-void function [-Wreturn-type]
   39 | }
      | ^
koala.cpp: In function 'int greaterValue(int, int, int, int)':
koala.cpp:75:1: warning: control reaches end of non-void function [-Wreturn-type]
   75 | }
      | ^

• Subtask 1: 4 / 4
• Subtask 2: 15 / 15
• Subtask 3: 18 / 18
• Subtask 4: 10 / 10
• Subtask 5: 29 / 53