Submission #242726

#	Time	Username	Problem	Language	Result	Execution time	Memory
242726		Theo830	Robots (IOI13_robots)	C++17	0 / 100	58 ms	65540 KiB

robots

#include <bits/stdc++.h>
#include "robots.h"
using namespace std;
typedef int ll;
ll INF = 2e9+7;
ll MOD = 99244353;
typedef pair<ll,ll> ii;
#define iii pair<ii,ll>
#define f(i,a,b) for(ll i = a;i < b;i++)
#define rf(i,a,b) for(long long i=a;i>=b;i--)
#define fastio ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define w(t) while(t--)
#define c(n); cin>>n;
#define p(n) cout<<n;
#define pl(n) cout<<n<<"\n";
#define ps(n); cout<<n<<" ";
#define F first
#define S second
#define pb(a) push_back(a)
#define all(x) (x).begin(), (x).end()
#define ull unsigned long long
#define vll vector<ll>
#define vii vector<ii>
#define mkp make_pair
#define ld long double
#define arrin(a,n) f(i,0,n){cin>>a[i];}
#define arrout(a,n) f(i,0,n){cout<<a[i]<<" ";}
#define printclock cerr<<"Time : "<<*(ld)clock()/(ld)CLOCKS_PER_SEC<<"ms\n";
#define PI (2*acos(0))
#define EPS 1e-18
const long long N = 1e5+5;
const long long M = 1e6+5;
vll visit,dist,taken;
vector<vll> adj;
vector<vii> adj2;
priority_queue<ii,vector<ii>, greater<ii> > pq;
ll bit[N-1]={0};
ll an[N][35];
ll depth[N]={0};
ll siz;
ll mycbrt(ll num){ll l = 1,r = 1000000;ll ans = 0;while(l <= r){ll mid = (l+r)/2;if(mid * mid * mid <= num){l = mid + 1;ans = max(ans,mid);}else{r = mid - 1;}}return ans;}
ll lcm(ll a,ll b){return (a * b) / __gcd(a,b);}
ll gcd(ll a,ll b){return __gcd(a,b);}
ll power(ll a,ll b){if(b == 0)return 1;if(b == 1)return a;ll ans = power(a,b/2) % MOD;ans *= ans;ans %= MOD;if(b % 2 == 1)ans *= a;return ans%MOD;}
ll inverse(ll x){x%=MOD;return power(x,MOD-2);}
void BITup(ll k, ll x){while(k <= siz){bit[k]+=x;k += k & -k;}}
ll BITq(ll k){ll s=0;while(k>=1){s+=bit[k];k -= k &-k;}return s;}
struct point{ll x,y,idx;};
void dfs(ll v){visit[v] = 1;for(auto x:adj[v]){if(!visit[x])dfs(x);}}
void bfs(ll s){visit[s] = 1;queue<ll>q;q.push(s);while(!q.empty()){ll u = q.front();ps(u);q.pop();for(auto x:adj[u]){if(!visit[x]){visit[x] = 1;q.push(x);}}}}
void dijkstra(ll s){pq.push(ii(0,s));dist[s] = 0;while(!pq.empty()){ii f = pq.top();pq.pop();ll w = f.F;ll u = f.S;if(w > dist[u]){continue;}for(auto v:adj2[u]){if(dist[u] + v.S < dist[v.F]){dist[v.F] = dist[u] + v.S;pq.push(ii(dist[v.F],v.F));}}}}
void prim(ll edge) {taken[edge] = 1;for(auto v:adj2[edge]) {if (taken[v.first]==0)pq.push(ii(v.second, v.first));}}
ll mst(ll s){taken.assign(N, 0);prim(s);ll cost = 0;while(!pq.empty()){ii front = pq.top();pq.pop();ll w = front.first;ll u = front.second;if(taken[u]==0)cost += w;prim(u);}return cost;}
void bfs01(ll s){deque<ll>q;dist[s] = 0;q.push_back(s);while(!q.empty()){ll v = q.front();q.pop_front();for(auto x:adj2[v]){if(dist[x.F] > dist[v] + x.S){dist[x.F] = dist[v] + x.S;if(x.S == 0){q.push_front(x.F);}else{q.push_back(x.F);}}}}}
void build(ll s,ll p){an[s][0] = p;f(i,1,35){an[s][i] = an[an[s][i-1]][i-1];}for(auto x:adj[s]){if(x != p){depth[x] = depth[s] + 1;build(x,s);}}}
ll kth(ll x,ll k){ll ans = x;if(depth[x] < k){return -1;}ll pos = 0;while(k > 0){if(k % 2){ans = an[ans][pos];}pos++;k /= 2;}return ans;}
ll lca(ll a,ll b){if(depth[a] > depth[b]){swap(a,b);}b = kth(b,abs(depth[a] - depth[b]));if(a == b){return a;}for(ll i = 34;i >= 0;i--){if(an[a][i] == an[b][i]){continue;}a = an[a][i];b = an[b][i];}return an[a][0];}
void YESNO(ll a){if(!!a){pl("YES");}else{pl("NO");}}
void filesin(void){freopen("a2.in","r",stdin);}
void filesout(void){freopen("ans.out","w",stdout);}
///I hope I will get uprating and don't make mistakes
///I will never stop programming
///sqrt(-1) Love C++
///Please don't hack me
///@TheofanisOrfanou Theo830
///Training
ll val(ii a){
    long long ans = (a.F * 2000000000) % MOD;
    ans *= a.S;
    ans %= MOD;
    return ans;
}
vector<ii>v1,v2;
ll sizee;
bool check(ll arr1[],ll arr2[],ll n,ll m,ll idx){
    ll res = 0;
    ll pos = 0;
    multiset<ii>exo;
    ll mp[MOD] = {0};
    f(j,0,n){
        while(pos < sizee && v1[pos].F < arr1[j]){
            exo.insert(ii(-v1[pos].S,v1[pos].F));
            pos++;
        }
        ll mm = idx;
        while(mm > 0 && !exo.empty()){
            ii el;
            for(auto x:exo){
                el = x;
                break;
            }
            exo.erase(exo.find(el));
            res++;
            if(res == sizee){
                return 1;
            }
            el.F = -el.F;
            mp[val(el)]++;
            mm--;
        }
    }
    pos = 0;
    f(j,0,m){
        ll mm = idx;
        while((mm > 0 && v2[pos].F < arr2[j]) && pos < sizee){
            if(mp[val(v2[pos])]){
                mp[val(v2[pos])]--;
                pos++;
            }
            else{
                res++;
                if(res == sizee){
                    return 1;
                }
                pos++;
                mm--;
            }
        }
    }
    return (res == sizee);
}
int putaway(int a, int b, int n, int x[], int y[], int w[], int s[]) {
    sizee = n;
    f(i,0,n){
        v1.pb(ii(w[i],s[i]));
        v2.pb(ii(s[i],w[i]));
    }
    sort(x,x+a);
    sort(y,y+b);
    sort(all(v1));
    sort(all(v2));
    ll l = 1,r = n;
    ll ans = INF;
    while(l <= r){
        ll mid = (l+r)/2;
        if(check(x,y,a,b,mid)){
            ans = min(ans,mid);
            r = mid - 1;
        }
        else{
            l = mid + 1;
        }
    }
    if(ans == INF){
        ans = -1;
    }
    return ans;
}
/*
int main(void){
    fastio;
    ll a,b,t;
    cin>>a>>b>>t;
    ll x[a],y[b],w[t],s[t];
    f(i,0,a){
        cin>>x[i];
    }
    f(i,0,b){
        cin>>y[i];
    }
    f(i,0,t){
        cin>>w[i]>>s[i];
    }
    cout<<putaway(a,b,t,x,y,w,s);
}
3 2 10
6 2 9
4 7
4 6
8 5
2 3
7 9
1 8
5 1
3 3
8 7
7 6
10 5
*/

Compilation message (stderr)

robots.cpp: In function 'void filesin()':
robots.cpp:59:27: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
 void filesin(void){freopen("a2.in","r",stdin);}
                    ~~~~~~~^~~~~~~~~~~~~~~~~~~
robots.cpp: In function 'void filesout()':
robots.cpp:60:28: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)', declared with attribute warn_unused_result [-Wunused-result]
 void filesout(void){freopen("ans.out","w",stdout);}
                     ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~

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