Submission #592590

#	Time	Username	Problem	Language	Result	Execution time	Memory
592590		fuad27	Robots (IOI13_robots)	C++17	0 / 100	1 ms	340 KiB

robots

#include "robots.h"
#include<bits/stdc++.h>
using namespace std;
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
int putaway(int A, int B, int T, int X[], int Y[], int W[], int S[]) {
//	if(B == 0) {
//		sort(X, X+A);
//		long long lo = 0, hi = 2*T;
//		long long res=-1;
//		while(lo <= hi) {
//			long long mid = (lo+hi)/2;
//			vector<long long> v(A);
//			for(long long i = 0;i<T;i++) {
//				long long it = upper_bound(X, X+A, W[i])-X;
//				if(it == A)return -1;
//				v[it]++;
//			}
//			for(long long i = 0;i<A-1;i++) {
//				if(v[i] > mid) {
//					v[i+1]+=v[i]-mid;
//					v[i]=mid;
//				}
//			}
//			if(v.back() > mid) {
//				lo = mid+1;
//			}
//			else {
//				res=mid;
//				hi=mid-1;
//			}
//		}
//		return res;
//	}
//	else if(A == 0) {
//		sort(Y, Y+B);
//		long long lo = 0, hi = 2*T;
//		long long res=-1;
//		while(lo <= hi) {
//			long long mid = (lo+hi)/2;
//			vector<long long> v(B);
//			for(long long i = 0;i<T;i++) {
//				long long it = upper_bound(Y, Y+B, S[i])-Y;
//				if(it == B)return -1;
//				v[it]++;
//			}
//			for(long long i = 0;i<B-1;i++) {
//				if(v[i] > mid) {
//					v[i+1]+=v[i]-mid;
//					v[i]=mid;
//				}
//			}
//			if(v.back() > mid) {
//				lo = mid+1;
//			}
//			else {
//				res=mid;
//				hi=mid-1;
//			}
//		}
//		return res;
//	}
	sort(X, X+A);
	sort(Y, Y+B);
	long long lo = 1, hi = 2*T;
	long long res=-1;
	while(lo <= hi) {
		long long mid = (lo+hi)/2;
		multiset<long long> v[A];
		multiset<long long> rem2;
		for(long long i = 0;i<T;i++) {
			long long it = upper_bound(X, X+A, W[i])-X;
			if(it == A)rem2.insert(S[i]);
			else v[it].insert(S[i]);
		}
		multiset<long long> rem;
		for(long long i = 0;i<A;i++) {
			while(v[i].size() > mid) {
				auto it = v[i].begin();
				rem.insert(*it);
				v[i].erase(it);
			}
			while(rem.size()>0 and v[i].size() < mid) {
				auto it = rem.end();
				--it;
				v[i].insert(*it);
				rem.erase(it);
			}
			int cnt = 0;
			while(rem.size() and v[i].size() and (*rem.begin()) >= (*v[i].begin())) {
				auto it = rem.begin();
				auto it2 = v[i].begin();
				v[i].insert(*it);
				rem.insert(*it2);
				rem.erase(it);
				v[i].erase(it2);
			}
 
		}
		for(auto it=rem2.begin();it!=rem2.end();it++) {
			rem.insert(*it);
		}
		bool check=1;
		vector<long long> v2(B);
		for(auto it=rem.begin();it!=rem.end();++it) {
			long long val = (*it);
			long long idx=upper_bound(Y, Y+B, val)-Y;
			if(idx==B){
				check=0;
				break;
			}
			v2[idx]++;
		}
		if(check) {
		for(long long i = 0;i<B-1;i++) {
			if(v2[i] > mid) {
				long long c = v2[i]-mid;
				v2[i+1]+=c;
				v2[i]=mid;
			}
		}
		}
		if(v2.back() > mid or !check) {
			lo = mid+1;
		}
		else {
			res=mid;
			hi = mid-1;
		}
	}
	return res;
}

Compilation message (stderr)

robots.cpp: In function 'int putaway(int, int, int, int*, int*, int*, int*)':
robots.cpp:78:22: warning: comparison of integer expressions of different signedness: 'std::multiset<long long int>::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
   78 |    while(v[i].size() > mid) {
      |          ~~~~~~~~~~~~^~~~~
robots.cpp:83:39: warning: comparison of integer expressions of different signedness: 'std::multiset<long long int>::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
   83 |    while(rem.size()>0 and v[i].size() < mid) {
      |                           ~~~~~~~~~~~~^~~~~
robots.cpp:89:8: warning: unused variable 'cnt' [-Wunused-variable]
   89 |    int cnt = 0;
      |        ^~~

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