제출 #235530

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
235530		crossing0ver	Robots (IOI13_robots)	C++17	53 / 100	811 ms	47808 KiB

robots

#include<bits/stdc++.h>
#define ll long long
#define ld long double
#include "robots.h"
using namespace std;
 // X weight  Y size
 int a,b,t,X[50001],Y[50001],W[1000001],S[1000001],mxW,mxS , flag = 1,kt[1000000][2];
 map<int,int> mp;
 ll sufa[50001],sufb[50001];
 ld mxa,mxb;
 vector<int> f,ds;
void count_max() {
	for (int i = 0; i < a; i++) mxW = max (mxW,X[i]);
	for (int i = 0; i < b; i++) mxS = max (mxS,Y[i]);
	for (int i = 0; i < t; i++) 
		if (W[i] >= mxW && S[i] >= mxS) flag = 0;
}
 
int case1() {
	if (a == 0) {
		if (Y[1] > S[1] && Y[0] > S[0]) return 1;
		return 2;
	}
	if (b == 0) {
		if (X[1] > W[1] && X[0] > W[0]) return 1;
		 return 2;
	}
	if ((X[0] > W[0] && Y[0] > S[1] ) || (X[0] > W[1] && Y[0] > S[0]) )
		return 1;
	return 0;
}
 
int case2() {
	set < pair<int,int> > s;
	int cnt = 0;
	for (int i = 0; i < t; i ++) s.insert ({W[i],cnt++});
	set<pair<int,int> > g;
	vector<int> v;
	for (int i = 0; i < a; i++) v.push_back(X[i]);
	int timer = 0;
	while (!s.empty()) {
		timer++;
		for (int j = 0,i; j < v.size() && s.size(); j++) {
			i = v[j];
			auto it  = s.lower_bound({i,0});
			if (it == s.begin()){
				if (j != v.size() - 1)
				swap(v[v.size() - 1],v[j]);
				v.pop_back();
				j--;
			}
			else {
				it--;
				s.erase(it);
			}
		}
	}
	return timer;
}
int bad[100000];
int case3() {
	/*vector<int> va,vb;
	for (int i = 0; i < a; i++) va.push_back(X[i]);
	for (int i = 0; i < b; i++) vb.push_back(Y[i]);  */
	int timer = 0;
		bool bigflag = 1;
		while(bigflag)  {
			
		bigflag = 0;
		
		for (int j = 0,ina,inb,i; j < a; j++) {
			 i = X[j];
			bool flag = 0;
			int maxa = 0, maxb= 0;
			for (int f = 0; f < t; f++) {
				if (!bad[f]) {
					if (W[f] < i) {
						if (maxa < W[f]) maxa = W[f], ina = f;
						if (maxb < S[f]) maxb = S[f], inb = f;
					flag = 1,bigflag = 1;
				}
				}
			}
			if (!flag) continue;
			if (mxa > mxb) {
				for (int i = 0; i < a; i++)
					if (X[i] > W[ina]) sufa[i] --;
				bad[ina]  =1;
			}
			else {
				for (int i = 0; i < b; i++)
					if (Y[i] <= W[inb]) sufb[i] --;
				bad[inb] = 1;
				
			}
			mxa = mxb= 0;
			for (int i = 0; i < a; i++) {
		mxa = max(mxa,(ld)sufa[i]/(a - i + 1));
	} 
	for (int i = 0; i < b; i++) {
		mxb = max(mxb,(ld)sufb[i]/(b - i + 1));
	} 
	}
	for (int j = 0,i,ina,inb; j < b; j++) {    int maxa = 0, maxb= 0;
		 	i = Y[j];
			bool flag = 0;
			for (int f = 0; f < t; f++) {
				if (!bad[f]) {
					if (S[f] < i) {
						if (maxa < W[f]) maxa = W[f], ina = f;
						if (maxb < S[f]) maxb = S[f], inb = f;
					flag = 1,bigflag = 1;
				}
				}
			}
			if (!flag) continue;
			if (mxa > mxb) {
				for (int i = 0; i < a; i++)
					if (X[i] > W[ina]) sufa[i] --;
				bad[ina]  =1;
			}
			else {
				for (int i = 0; i < b; i++)
					if (Y[i] <= W[inb]) sufb[i] --;
				bad[inb] = 1;
				
			}  mxa = mxb= 0;
			for (int i = 0; i < a; i++) {
		mxa = max(mxa,(ld)sufa[i]/(a - i + 1));
	} 
	for (int i = 0; i < b; i++) {
		mxb = max(mxb,(ld)sufb[i]/(b - i + 1));
	} 
	}
	if (bigflag) timer++;
	}
	return timer;
}
 
int putaway(int A1, int B1, int T1, int X1[], int Y1[], int W1[], int S1[]) {
	a = A1; b = B1;t = T1;
	for (int i = 0; i < a; i++) X[i] = X1[i],f.push_back(X[i]);
	for (int i = 0; i < b; i++) Y[i] = Y1[i],f.push_back(Y[i]);
	for (int i = 0; i < t; i++) W[i] = W1[i], S[i] = S1[i],f.push_back(W[i]),f.push_back(W[i]);
	sort (X, X + a);
	sort (Y, Y + b);
	int last = INT_MIN;
	int cnt = 0;
    count_max();
    if (!flag) return -1;
    if (b == 0)	return case2();
    if (t == 2 && a + b == 2) return case1();
    	for (int i = a-1; i >= 0; i--) {
		sufa[i] = sufa[i+1];
		for (int j = 0; j < t; j++)
			if (W[j] < X[i] && !kt[j][0]) sufa[i]++,kt[j][0] = 1;
	}
	for (int i = b - 1; i >= 0; i--) {
		for (int j = 0; j < t; j++)
			if (S[j] < Y[i] && !kt[j][1]) sufb[i]++,kt[j][1] = 1;
	}
	for (int i = b - 1; i >= 0; i--) {
		sufb[i] += sufb[i+1];
	}
	for (int i = a - 1; i >= 0; i--) {
		sufa[i] += sufa[i+1];
	}
	for (int i = 0; i < a; i++) {
		mxa = max(mxa,(ld)sufa[i]/(a - i + 1));
	} 
	for (int i = 0; i < b; i++) {
		mxb = max(mxb,(ld)sufb[i]/(b - i + 1));
	}
    return case3();
}

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

robots.cpp: In function 'int case2()':
robots.cpp:43:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int j = 0,i; j < v.size() && s.size(); j++) {
                     ~~^~~~~~~~~~
robots.cpp:47:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     if (j != v.size() - 1)
         ~~^~~~~~~~~~~~~~~
robots.cpp: In function 'int putaway(int, int, int, int*, int*, int*, int*)':
robots.cpp:147:6: warning: unused variable 'last' [-Wunused-variable]
  int last = INT_MIN;
      ^~~~
robots.cpp:148:6: warning: unused variable 'cnt' [-Wunused-variable]
  int cnt = 0;
      ^~~
robots.cpp: In function 'int case3()':
robots.cpp:124:23: warning: 'inb' may be used uninitialized in this function [-Wmaybe-uninitialized]
      if (Y[i] <= W[inb]) sufb[i] --;
                  ~~~~~^
robots.cpp:92:23: warning: 'inb' may be used uninitialized in this function [-Wmaybe-uninitialized]
      if (Y[i] <= W[inb]) sufb[i] --;
                  ~~~~~^

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