Submission #387510

#	Time	Username	Problem	Language	Result	Execution time	Memory
387510		ACmachine	Teams (IOI15_teams)	C++17	77 / 100	1240 ms	32612 KiB

teams

#include "teams.h"
#include <bits/stdc++.h>
using namespace std;
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;

template<typename T> using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
template<typename T, typename U> using ordered_map = tree<T, U, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

typedef long long ll;
typedef long double ld;

typedef pair<int,int> pii;
typedef pair<ll,ll> pll;

typedef vector<int> vi;
typedef vector<ll> vll;

#define FOR(i,j,k,in) for(int i=(j); i < (k);i+=in)
#define FORD(i,j,k,in) for(int i=(j); i >=(k);i-=in)
#define REP(i,b) FOR(i,0,b,1)
#define REPD(i,b) FORD(i,b,0,1)
#define pb push_back
#define mp make_pair
#define ff first
#define ss second
#define all(x) begin(x), end(x)
#define MANY_TESTS int tcase; cin >> tcase; while(tcase--)

const double EPS = 1e-9;
const int MOD = 1e9+7;
const ll INFF = 1e18;
const int INF = 1e9;
const ld PI = acos((ld)-1);
const vi dy = {1, 0, -1, 0, -1, 1, 1, -1};
const vi dx = {0, 1, 0, -1, -1, 1, -1, 1};

void DBG(){cout << "]" << endl;}
template<typename T, typename ...U> void DBG(const T& head, const U... args){ cout << head << "; "; DBG(args...); }
#define dbg(...) cout << "Line(" << __LINE__ << ") -> [" << #__VA_ARGS__ << "]: [", DBG(__VA_ARGS__);
#define chk() cout << "Check at line(" << __LINE__ << ") hit." << endl;

template<class T, unsigned int U>
ostream& operator<<(ostream& out, const array<T, U> &v){out << "[";  REP(i, U) out << v[i] << ", ";  out << "]"; return out;}
template <class T, class U>
ostream& operator<<(ostream& out, const pair<T, U> &par) {out << "[" << par.first << ";" << par.second << "]"; return out;}
template <class T>
ostream& operator<<(ostream& out, const set<T> &cont) { out << "{"; for( const auto &x:cont) out << x << ", "; out << "}"; return out; }
template <class T, class U>
ostream& operator<<(ostream& out, const map<T, U> &cont) {out << "{"; for( const auto &x:cont) out << x << ", "; out << "}"; return out; }
template<class T>
ostream& operator<<(ostream& out, const vector<T> &v){ out << "[";  REP(i, v.size()) out << v[i] << ", ";  out << "]"; return out;}

template<class T>
istream& operator>>(istream& in, vector<T> &v){ for(auto &x : v) in >> x; return in; }

vector<int> b;
int n;


template<int M>
struct bit{
    static const int blocks = (M >> 6) + 2;
    unsigned long long a[blocks];
    bit(){memset(a, 0, sizeof(a));}
    void NOT(){REP(i, blocks) a[i] = ~a[i];}
    void AND(bit<M> &oth){
        REP(i, blocks) a[i] &= oth.a[i];
    }
    void REM(bit<M> &oth){
        REP(i, blocks) a[i] &= (~oth.a[i]);
    }
    void OR(bit<M> &oth){
        REP(i, blocks) a[i] |= oth.a[i];
    }
    void set(int id){
        int bid = (id >> 6);
        id -= (bid << 6);
        a[bid] |= (1ull << id);
    }
    bool get_first(int x){
        int curr = 0;
        int nxt = INF;
        bool is_enough = false;
        REP(i, blocks){
            curr += __builtin_popcountll(a[i]);
            if(curr >= x){
                is_enough = true;
                nxt = i + 1;
                REPD(j, 63){
                    if(a[i] & (1ull << j)){
                        if(curr > x){
                            a[i] &= ~(1ull << j);
                            curr--;
                        }
                    }
                }
                break;
            }
        }
        FOR(i, nxt, blocks, 1)
            a[i] = 0;
        return is_enough;
    }
    void reset_until_time(int time){
        REP(i, blocks){
            int mtime = ((i << 6) + 63);
            if(mtime >= n) mtime = INF;
            else mtime = b[mtime];
            if(mtime <= time)
                a[i] = 0;
            else{
                REPD(j, 63){
                    if(a[i] & (1ull << j)){
                        if(b[(i<<6) + j] <= time)
                            a[i] &= ~(1ull << j);
                    }
                }
                break;
            }
        }
    }
    void print(int nm){
        REP(i, nm){
            REP(j, 64){
                cout << ((a[i] & (1ull << j)) ? 1 : 0);
            }
        }
        cout << endl;
    }
};
const int mxn = (int)1e5;
vector<bit<mxn>> bits;
vector<int> pos;
vector<int> a;
vector<int> as;
vector<int> pp_ar;
vector<int> Ain;
int cutoff = 50;
void init(int N, int A[], int B[]) {
    n = N;
    REP(i, N) b.pb(B[i]);
    REP(i, N) Ain.pb(A[i]);
    sort(all(b));
    vector<int> bs(N);
    pos.resize(N);
    REP(i, N) bs[i] = i;
    auto cmp = [&](int lhs, int rhs){
        return B[lhs] < B[rhs];
    };
    auto cmp_a = [&](int lhs, int rhs){
        return A[lhs] < A[rhs];
    };
    sort(all(bs), cmp);
    REP(i, N) pos[bs[i]] = i;
    as.resize(n);
    REP(i, n) as[i] = i;
    sort(all(as), cmp_a);
    int pp = 0;
    int pp2 = 0; // on b
    bit<mxn> bt;
    vector<int> na;
    REP(i, N) na.pb(A[i]);
    sort(all(na));
    na.erase(unique(all(na)), na.end());
    int prev_pp = -1000;
    REP(i, na.size()){
        while(pp < as.size() && A[as[pp]] <= na[i]){
            bt.set(pos[as[pp]]); pp++;
        }
        if(pp > prev_pp + cutoff){
            a.pb(na[i]);
            bits.pb(bt);
            pp_ar.pb(pp);
            prev_pp = pp;
        }
    }
}

int can(int M, int K[]) {
    sort(K, K + M);
    bit<mxn> removed;
    bit<mxn> temp;
    REP(i, M){
        int id = upper_bound(all(a), K[i]) - a.begin();
        id--;
        if(id == -1) return 0;
        temp = bits[id];
        int pp = pp_ar[id];
        while(pp < as.size() && Ain[as[pp]] <= K[i]){
            temp.set(pos[as[pp]]);
            pp++;
        }
        temp.reset_until_time(K[i] - 1);
        temp.REM(removed);
        if(!temp.get_first(K[i])){
            return 0;
        }
        removed.OR(temp);
        //dbg(i, id, K[i])
        //removed.print(1);
    }
    return 1;
}

Compilation message (stderr)

teams.cpp: In function 'void init(int, int*, int*)':
teams.cpp:20:40: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   20 | #define FOR(i,j,k,in) for(int i=(j); i < (k);i+=in)
      |                                        ^
teams.cpp:22:18: note: in expansion of macro 'FOR'
   22 | #define REP(i,b) FOR(i,0,b,1)
      |                  ^~~
teams.cpp:168:5: note: in expansion of macro 'REP'
  168 |     REP(i, na.size()){
      |     ^~~
teams.cpp:169:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  169 |         while(pp < as.size() && A[as[pp]] <= na[i]){
      |               ~~~^~~~~~~~~~~
teams.cpp:161:9: warning: unused variable 'pp2' [-Wunused-variable]
  161 |     int pp2 = 0; // on b
      |         ^~~
teams.cpp: In function 'int can(int, int*)':
teams.cpp:186:44: warning: conversion from '__gnu_cxx::__normal_iterator<int*, std::vector<int> >::difference_type' {aka 'long int'} to 'int' may change value [-Wconversion]
  186 |         int id = upper_bound(all(a), K[i]) - a.begin();
      |                  ~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~
teams.cpp:191:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  191 |         while(pp < as.size() && Ain[as[pp]] <= K[i]){
      |               ~~~^~~~~~~~~~~

• Subtask 1: 21 / 21
• Subtask 2: 13 / 13
• Subtask 3: 43 / 43
• Subtask 4: 0 / 23