Thieves and Prisons

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef long double ld;
typedef vector<ll> vi;
typedef pair<ll,ll> ii;
typedef vector<ii> vii;
#define rep(i,a,b) for(int i = a; i < b; i++)
#define per(i,a,b) for(int i = a; i >= b; i--)
#define inf 9000000000000000000
#define all(x) x.begin(),x.end()
#define sz(x) (ll)(x).size()
#define trav(a,x) for(auto& a : x)

int main(){
  ios::sync_with_stdio(0);
  ll n,k,m,x,c = 0;
  char t;
  cin >> n >> k >> m;
  vi xs,tp,ans;
  rep(i,0,m){
    cin >> t >> x; x--;
    if (t == 'C') tp.push_back(1);
    else tp.push_back(0);
    xs.push_back(x);
  }

  if (k == 2 && m <= 10){
    rep(tmp,0,(1<<m)){
      ans.assign(m,0);
      rep(i,0,m){
        if (tmp&(1<<i)) ans[i] = 1;
        else ans[i] = 2;
      }

      vector<vi> prisons;
      vi _,fre;
      prisons.assign(m,_);
      fre.assign(m,1);
      bool works = true;
      rep(i,0,m){
        if (tp[i]){
          if (fre[xs[i]]) { fre[xs[i]] = 0; prisons[ans[i]-1].push_back(xs[i]); }
          else { works = false; break; }
        } else {
          if (!fre[xs[i]]) { works = false; break; }
          if (sz(prisons[ans[i]-1]) == 0) { works = false; break; }
          trav(x,prisons[ans[i]-1]) fre[x] = 1;
          prisons[ans[i]-1].clear();
        }
      }

      if (works) {
        rep(i,0,m) cout << ans[i] << " ";
        cout << endl;
        exit(0);
      }
    }
    cout << "IMPOSSIBLE" << endl; exit(0);
  }

  vi lst,prev,cnt;
  set<ll> os,cur;
  lst.assign(n,-1);
  prev.assign(m,-1);
  ans.assign(m,-1);
  cnt.assign(m+1,0);
  rep(i,0,m){
    if (lst[xs[i]] != -1) prev[i] = lst[xs[i]];
    if (tp[i] == 0) { ans[i] = (c%k)+1; cnt[i] = c; c++; os.insert(i); cur.insert(i); }
    else lst[xs[i]] = i;
  }
  cnt[m] = c;
  cnt[m] = c;
  cur.insert(m);
  os.insert(m);

  //rep(i,0,m) cout << prev[i] << " "; cout << endl;
  //rep(i,0,m) cout << ans[i] << " "; cout << endl;

  rep(i,0,m){
    //trav(i,os) cout << i << " "; cout << endl;
    //trav(i,cur) cout << i << " "; cout << endl;

    if (prev[i] == -1) continue;
    ll hi = i, lo = prev[i];
    set<ll>::iterator a = upper_bound(all(cur),lo);
    set<ll>::iterator _a = lower_bound(all(os),hi);
    set<ll>::iterator b = upper_bound(all(os),lo);
    set<ll>::iterator c = lower_bound(all(os),(*a));
    if ((*b) == m) { cout << "IMPOSSIBLE" << endl; exit(0); }
    //cout << " " << (*a) << " " << (*_a) << endl;
    if (cnt[(*c)]-cnt[(*b)] >= k) { ans[lo] = ans[(*b)]; }
    else if ((*a) >= (*_a)) { ans[lo] = ans[(*b)]; }
    else { ans[lo] = ans[(*a)]; cur.erase(a); }
  }
  rep(i,0,m) if (ans[i] == -1) ans[i] = 1;

  vector<vi> prisons;
  vi _,fre;
  prisons.assign(m,_);
  fre.assign(m,1);
  rep(i,0,m){
    if (tp[i]){
      if (fre[xs[i]]) { fre[xs[i]] = 0; prisons[ans[i]-1].push_back(xs[i]); }
      else { cout << "IMPOSSIBLE" << endl; exit(0); }
    } else {
      if (!fre[xs[i]]) { cout << "IMPOSSIBLE" << endl; exit(0); }
      if (sz(prisons[ans[i]-1]) == 0) { cout << "IMPOSSIBLE" << endl; exit(0); }
      trav(x,prisons[ans[i]-1]) fre[x] = 1;
      prisons[ans[i]-1].clear();
    }
  }

  rep(i,0,m) cout << ans[i] << " ";
  cout << endl;
}

Test 1

Group: 2, 4, 5

Verdict: ACCEPTED

Test 2

Group: 2, 4, 5

Verdict: ACCEPTED

Test 3

Group: 2, 4, 5

Verdict: ACCEPTED

Test 4

Group: 2, 4, 5

Verdict: ACCEPTED

Test 5

Group: 2, 4, 5

Verdict: ACCEPTED

Test 6

Group: 4, 5

Verdict: ACCEPTED

Test 7

Group: 4, 5

Verdict: ACCEPTED

Test 8

Group: 4, 5

Verdict: ACCEPTED

Test 9

Group: 1, 3, 4, 5

Verdict: ACCEPTED

Test 10

Group: 1, 3, 4, 5

Verdict: ACCEPTED

Test 11

Group: 1, 3, 4, 5

Verdict: ACCEPTED

Test 12

Group: 1, 3, 4, 5

Verdict: ACCEPTED

Test 13

Group: 1, 3, 4, 5

Verdict: ACCEPTED

Test 14

Group: 1, 3, 4, 5

Verdict: ACCEPTED

Test 15

Group: 1, 3, 4, 5

Verdict: ACCEPTED

Test 16

Group: 1, 3, 4, 5

Verdict: ACCEPTED

Test 17

Group: 1, 2, 3, 4, 5

Verdict: ACCEPTED

Test 18

Group: 1, 3, 4, 5

Verdict: ACCEPTED

Test 19

Group: 2, 5

Verdict: TIME LIMIT EXCEEDED

Test 20

Group: 2, 5

Verdict: ACCEPTED

Test 21

Group: 2, 5

Verdict: TIME LIMIT EXCEEDED

Test 22

Group: 5

Verdict: ACCEPTED

Test 23

Group: 5

Verdict: ACCEPTED

Test 24

Group: 3, 4, 5

Verdict: WRONG ANSWER

Test 25

Group: 3, 4, 5

Verdict: WRONG ANSWER

Test 26

Group: 3, 4, 5

Verdict: WRONG ANSWER

Test 27

Group: 3, 4, 5

Verdict: WRONG ANSWER

Test 28

Group: 4, 5

Verdict: WRONG ANSWER

Test 29

Group: 4, 5

Verdict: WRONG ANSWER

Test 30

Group: 4, 5

Verdict: WRONG ANSWER

Test 31

Group: 4, 5

Verdict: WRONG ANSWER

Test 32

Group: 2, 4, 5

Verdict: WRONG ANSWER

Test 33

Group: 2, 4, 5

Verdict: WRONG ANSWER

Test 34

Group: 2, 4, 5

Verdict: WRONG ANSWER

Test 35

Group: 2, 4, 5

Verdict: WRONG ANSWER

Test 36

Group: 3, 5

Verdict: TIME LIMIT EXCEEDED

Test 37

Group: 3, 5

Verdict: TIME LIMIT EXCEEDED

Test 38

Group: 3, 5

Verdict: TIME LIMIT EXCEEDED

Test 39

Group: 3, 5

Verdict: TIME LIMIT EXCEEDED

Test 40

Group: 5

Verdict: TIME LIMIT EXCEEDED

Test 41

Group: 5

Verdict: TIME LIMIT EXCEEDED

Test 42

Group: 5

Verdict: TIME LIMIT EXCEEDED

Test 43

Group: 5

Verdict: TIME LIMIT EXCEEDED

Test 44

Group: 2, 5

Verdict: TIME LIMIT EXCEEDED

Test 45

Group: 2, 5

Verdict: TIME LIMIT EXCEEDED

Test 46

Group: 2, 5

Verdict: TIME LIMIT EXCEEDED

Test 47

Group: 2, 5

Verdict: TIME LIMIT EXCEEDED