제출 #635708

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
635708		shmad	코알라 (APIO17_koala)	C++17	47 / 100	56 ms	456 KiB

koala

            #include <bits/stdc++.h>
             
            #ifndef ONLINE_JUDGE
            	#include "koala.h"
            #endif
             
            #define vt vector
            #define pb push_back
            #define all(x) (x).begin(), (x).end()
            #define sz(x) (int)(x).size()
            #define ff first
            #define ss second
            #define dbg(x) cerr << #x << " = " << x << '\n'
            #define bit(x, i) ((x) >> (i) & 1)
             
            using namespace std;
            using ll = long long;
            using pii = pair<int, int>;
            using vvt = vt< vt<int> >;
             
            #ifdef ONLINE_JUDGE
             
            static int maxQueries = 3200;
            static int numQueries;
             
            static void runGame(int F);
            static void grader();
             
            int main() {
                grader();
                return 0;
            }

	       #endif
             
 /*          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];
                }
            }
             
            #endif  */
        
             
            int a[100], b[100];
             
            int minValue(int n, int w) {  
                fill(a, a + n, 0);
                a[0] = 1;
                playRound(a, b);
                for (int i = 1; i < n; i++) if (b[i] == 0) return i;
                return 0;
            }
             
            int maxValue (int n, int w) {
            	vt<int> p(n);
            	iota(all(p), 0ll);
            	while (sz(p) != 1) {
            		fill(a, a + n, 0);
            		int x = w / sz(p);
            		for (int i: p) a[i] = x;
            		playRound(a, b);
            		p.clear();
            		for (int i = 0; i < n; i++) if (b[i] == x + 1) p.pb(i);
            	}
                return p[0];
            }
             
            int greaterValue (int n, int w) {
            	fill(a, a + n, 0);
            	int l = 1, r = 13, ans = 0;
            	while (l <= r) {
            		int mid = l + r >> 1;
            		fill(a, a + n, 0);
            		a[0] = a[1] = mid;
            		playRound(a, b);
            		if (b[0] != b[1]) return (b[0] < b[1]);
            		if (b[0] > mid && b[1] > mid) ans = mid, l = mid + 1;
            		else r = mid - 1;
            	}
            	a[0] = a[1] = ans;
            	playRound(a, b);
            	return (b[0] < b[1]);
            }
             
            bool check (int i, int j, int n, int w) {
            	fill(a, a + n, 0);
            	a[i] = a[j] = w / 2;
            	playRound(a, b);
            	return (b[j] > w / 2);
            }
             
            vt<int> merge_sort (vt<int> &a, int n, int w) {
            	if (sz(a) == 1) return a;
            	vt<int> l, r;
            	for (int i = 0; i < sz(a); i++) {
            		if (i < sz(a) / 2) l.pb(a[i]);
            		else r.pb(a[i]);
            	}
            	l = merge_sort(l, n, w);
            	r = merge_sort(r, n, w);
            	a.clear();
            	int i = 0, j = 0;
            	while (i < sz(l) && j < sz(r)) a.pb((check(l[i], r[j], n, w) ? l[i++] : r[j++]));
            	while (i < sz(l)) a.pb(l[i++]);
            	while (j < sz(r)) a.pb(r[j++]);
            	return a;
            }
             
            bool cmp (int i, int j) {
            	int l = 1, r = 13, ans = 0;
            	while (l <= r) {
            		int mid = l + r >> 1;
            		memset(a, 0, sizeof(a));
            		a[i] = a[j] = mid;
            		playRound(a, b);
            		if (b[i] != b[j]) return (b[i] < b[j]);
            		if (b[i] > mid && b[j] > mid) ans = mid, l = mid + 1;
            		else r = mid - 1;
            	}
            	a[i] = a[j] = ans;
            	playRound(a, b);
            	return (b[i] < b[j]);
            }
         
            static int N = 100, W = 100;
            static int P[105];
         
            void get(int *B, int *R) {
                int i, j;
                
             
                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];
                }
            }
             
            void allValues (int n, int w, int *p) {
                if (w == n * 2) {
                    vt<int> v(n);
                	iota(all(v), 0ll);	
                	v = merge_sort(v, n, w);
                	for (int i = 0; i < n; i++) p[v[i]] = i + 1;
                	return;
                }                 
              	for (int i = 0; i < 100; i++) playRound(a, b);
                fill(p, p + n, 0);
                int cur = 0;
                while (cur < n) {
                	vt<int> v;
                    for (int i = 0; i < n; i++) if (p[i] == 0) v.pb(i);
                    int x = 1;
                    while (sz(v) != 1) {
                    	fill(a, a + n, 0);
                    	for (int i: v) a[i] = x;
                    	get(a, b);
                    	vt<int> nv;
                    	for (int i: v) if (b[i] == x + 1) nv.pb(i);
                    	if (sz(nv) == 0) x--;
                    	else v = nv, x *= 2;
                    }
                    p[v[0]] = n - cur++;
                }
            }
             
            #ifdef ONLINE_JUDGE
            static void runGame(int F) {
                int i;
             
                scanf("%d %d",&N,&W);
                for (i=0;i<N;++i) {
                    scanf("%d",&P[i]);
                }
             
                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);
            }
             
            static void grader() {
                int i;
             
                int F, G;
                scanf("%d %d",&F,&G);
             
                for (i=0;i<G;i++) {
                    runGame(F);
                }
            }
            #endif

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

koala.cpp: In function 'int greaterValue(int, int)':
koala.cpp:127:27: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  127 |               int mid = l + r >> 1;
      |                         ~~^~~
koala.cpp: In function 'bool cmp(int, int)':
koala.cpp:167:27: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  167 |               int mid = l + r >> 1;
      |                         ~~^~~

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