Submission #65336

#	Time	Username	Problem	Language	Result	Execution time	Memory
65336		boook	Robots (IOI13_robots)	C++14	0 / 100	3 ms	672 KiB

robots

#include "robots.h"
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace std;
using namespace __gnu_pbds;
#define REP(i,j,k)     for(int i = j ; i < k ; ++i)
#define RREP(i,j,k)    for(int i = j ; i >=k ; --i)
#define A    first
#define B    second
#define mp   make_pair
#define pb   emplace_back
#define PII pair<int , int>
#define MEM(i,j)   memset(i , j , sizeof i)
#define ALL(i)     i.begin() , i.end()
#define DBGG(i,j)     cout << i << " " << j << endl
#define DB4(i,j,k,l)  cout << i << " " << j << " " << k << " " << l << endl
#define IOS cin.tie(0) , cout.sync_with_stdio(0)
#define endl "\n"
///------------------------------------------------------------
#define MAX 1010
#define INF 0x3f3f3f3f

int sum[MAX][MAX] , sss[60000];
int putaway(int a, int b, int n, int x[], int y[], int w[], int s[]) {
	if(b == 0){
		sort(x , x + a) , a[x] = 2123456789;
		REP(i , 0 , n){
			if(x[a - 1] <= w[i]) return -1;
			else {
				int v1 = upper_bound(x , x + a + 1 , w[i]) - x;
				sss[a - v1] ++;
			}
		}
		REP(i , 1 , a + 1) sss[i] += sss[i - 1];
		int ans = n;
		RREP(base , 20 , 0){
			int to = ans - (1 << base);
			if(to >= 1){
				int ok = 1;
				REP(i , 0 , a + 1) if(i * to < sss[i]){
					ok = 0;
					break;
				}
				if(ok == 1) ans = to;
			}
		}
	}
	else {
		sort(x , x + a) , a[x] = 2123456789;
		sort(y , y + b) , b[y] = 2123456789;
		REP(i , 0 , n){
			if(x[a - 1] <= w[i] && y[b - 1] <= s[i]) return -1;
			else {
				int v1 = upper_bound(x , x + a + 1 , w[i]) - x;
				int v2 = upper_bound(y , y + b + 1 , s[i]) - y;
				sum[a - v1][b - v2] ++;
			}
		}
		REP(i , 0 , a + 1) REP(j , 0 , b + 1){
			if(i - 1 >= 0) sum[i][j] += sum[i - 1][j];
			if(j - 1 >= 0) sum[i][j] += sum[i][j - 1];
			if(i - 1 >= 0 && j - 1 >= 0) sum[i][j] -= sum[i - 1][j - 1];
		}
		int ans = n;
		RREP(base , 20 , 0){
			int to = ans - (1 << base);
			if(to >= 1){
				int ok = 1;
				REP(i , 0 , a + 1) REP(j , 0 , b + 1){
					if((i + j) * to < sum[i][j]){
						ok = 0;
						break;
					}
				}
				if(ok == 1) ans = to;
			}
		}
	    return ans;
	}
}

Compilation message (stderr)

robots.cpp: In function 'int putaway(int, int, int, int*, int*, int*, int*)':
robots.cpp:80:1: warning: control reaches end of non-void function [-Wreturn-type]
 }
 ^

• Subtask 1: 0 / 14
• Subtask 2: 0 / 14
• Subtask 3: 0 / 25
• Subtask 4: 0 / 37
• Subtask 5: 0 / 10