제출 #310219

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
310219		amunduzbaev	로봇 (IOI13_robots)	C++14	100 / 100	2296 ms	57996 KiB

robots

#include "robots.h"
//#include "grader.cpp"
#include <bits/stdc++.h>
using namespace std;
const int inf=1e9+7;
multiset< pair<int, int> >wt, st, r;
int solve(){

    int ans=0;
    while(wt.size()>0&&st.size()>0){
        ans++;
        vector<pair<int,int>>del;
        for(auto x:r){
            if(!wt.size()&&!st.size()) break;
            int robot=x.first;
            int type=x.second;

            //cout<<robot<<"\n";

            if(type == 0)
            {
                auto toy =  wt.upper_bound({robot,-inf});
                if(toy == wt.begin()) {
                    del.push_back(x);
                    continue;
                }
                toy--;
                int wtoy = (*toy).first;
                int stoy = (*toy).second;

                wt.erase( wt.find( {wtoy,stoy} ) );
                st.erase( st.find( {stoy,wtoy} ) );

            }
            else
            {
                auto toy =  st.upper_bound({robot,-inf});
                if(toy == st.begin()){
                    del.push_back(x);
                    continue;
                }
                toy--;
                int stoy = (*toy).first;
                int wtoy = (*toy).second;

                wt.erase( wt.find( {wtoy,stoy} ) );
                st.erase( st.find( {stoy,wtoy} ) );
				//cout<<"works\n";
            }
            //cout<<wt.size()<<"\n";
        }
        for(auto x:del){
            r.erase(x);
        }

    }

    return ans;
}
int putaway(int a, int b, int t, int a1[], int b1[], int w[], int s[]) {
    sort(a1,a1+a);
    sort(b1,b1+b);
    int mxa=(a>0 ? a1[a-1]:0),mxb=(b>0 ? b1[b-1]:0);
    for(int i=0;i<t;i++){
        if(w[i]>=mxa&&s[i]>=mxb) return -1;

        wt.insert({w[i],s[i]});
        st.insert({s[i],w[i]});
    }
    for(int i=0;i<a;i++) r.insert({a1[i],0});
    for(int i=0;i<b;i++) r.insert({b1[i],1});
    int ans=solve();

    return ans;
}
/*
2 0 2
20 10
10 7
10 13

    */

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