Submission #648923

#	Time	Username	Problem	Language	Result	Execution time	Memory
648923		ymm	The Big Prize (IOI17_prize)	C++17	0 / 100	1 ms	336 KiB

prize

    #include "prize.h"
    #include <bits/stdc++.h>
    #define Loop(x,l,r) for (ll x = (l); x < (ll)(r); ++x)
    #define LoopR(x,l,r) for (ll x = (r)-1; x >= (ll)(l); --x)
    typedef long long ll;
    typedef std::pair<int, int> pii;
    typedef std::pair<ll , ll > pll;
    using namespace std;
     
    static const int N = 200'010;
    static int cnt[N];
     
    static int test(int *a, int n)
    {
    	fill(cnt, cnt+n, 0);
    	int pos = -1;
    	int mx = 1;
    	Loop (i,0,n) {
    		if (a[i] > n || 1 > a[i])
    			return -1;
    		if (a[i] > mx)
    			mx = a[i];
    		if (a[i] == 1)
    			pos = i;
    		cnt[a[i]-1]++;
    	}
    	if (cnt[0] != 1)
    		return -1;
    	Loop (i,0,mx-1)
    		if ((ll)cnt[i] * cnt[i] >= cnt[i+1])
    			return -1;
    	return pos;
    }
     
    static bool test_is_vector(void *add, int n)
    {
    	ll *p = (ll *)add;
    	ll len = p[1] - p[0];
    	ll cap = p[2] - p[0];
    	if (len != n*sizeof(int))
    		return 0;
    	if (len > cap)
    		return 0;
    	if ((cap & -cap) != cap) // cap = 2^k
    		return 0;
    	return 1;
    }
     
    int find_best(int n)
    {
    	ll dard = 0;
    	bool find_vec = 0;
    	for (void *add = &dard; add < &dard + 2048; add += 8) {
    		if (!test_is_vector(add, n))
    			continue;
    		find_vec = 1;
          return -2;
    		int tmp = test(*(int **)add, n);
    		if (tmp != -1)
    			return tmp;
    	}
    	return -(1 + find_vec);
    }

Compilation message (stderr)

prize.cpp: In function 'bool test_is_vector(void*, int)':
prize.cpp:40:14: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'long unsigned int' [-Wsign-compare]
   40 |      if (len != n*sizeof(int))
      |          ~~~~^~~~~~~~~~~~~~~~
prize.cpp: In function 'int find_best(int)':
prize.cpp:53:54: warning: pointer of type 'void *' used in arithmetic [-Wpointer-arith]
   53 |      for (void *add = &dard; add < &dard + 2048; add += 8) {
      |                                                  ~~~~^~~~
prize.cpp:53:42: warning: array subscript 2048 is outside array bounds of 'll [1]' {aka 'long long int [1]'} [-Warray-bounds]
   53 |      for (void *add = &dard; add < &dard + 2048; add += 8) {
      |                                    ~~~~~~^~~~~~
prize.cpp:51:9: note: while referencing 'dard'
   51 |      ll dard = 0;
      |         ^~~~

• Subtask 1: 0 / 20
• Subtask 2: 0 / 80