CSES - NOI 2019

Submission details
Task:	Distance Code
Sender:	Hugo Eberhard
Submission time:	2019-03-06 14:22:49 +0200
Language:	C++
Status:	READY
Result:	0

Feedback
group	verdict	score
#1	WRONG ANSWER	0
#2	WRONG ANSWER	0
#3	WRONG ANSWER	0

Test results
test	verdict	time	group
#1	WRONG ANSWER	0.02 s	1, 2, 3	details
#2	WRONG ANSWER	0.02 s	1, 2, 3	details
#3	RUNTIME ERROR	0.02 s	1, 2, 3	details
#4	WRONG ANSWER	0.02 s	1, 2, 3	details
#5	RUNTIME ERROR	0.01 s	1, 2, 3	details
#6	WRONG ANSWER	0.01 s	1, 2, 3	details
#7	RUNTIME ERROR	0.02 s	1, 2, 3	details
#8	RUNTIME ERROR	0.02 s	1, 2, 3	details
#9	WRONG ANSWER	0.01 s	1, 2, 3	details
#10	RUNTIME ERROR	0.02 s	1, 2, 3	details
#11	RUNTIME ERROR	0.01 s	1, 2, 3	details
#12	RUNTIME ERROR	0.02 s	2, 3	details
#13	RUNTIME ERROR	0.02 s	2, 3	details
#14	RUNTIME ERROR	0.02 s	2, 3	details
#15	RUNTIME ERROR	0.02 s	2, 3	details
#16	RUNTIME ERROR	0.50 s	3	details
#17	RUNTIME ERROR	0.73 s	3	details
#18	RUNTIME ERROR	0.04 s	3	details
#19	RUNTIME ERROR	0.34 s	3	details
#20	WRONG ANSWER	0.02 s	1, 2, 3	details

Code

#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;
  }

  vi lst,prev,cnt;
  set<ll> os,cur;
  lst.assign(n,-1);
  prev.assign(m,-1);
  ans.assign(m,-1);
  cnt.assign(m,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;
  }
  cur.insert(m+10);
  os.insert(m+10);

  //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));
    //cout << " " << (*a) << " " << (*_a) << endl;
    if (cnt[(*c)]-cnt[(*b)] >= k) { ans[lo] = ans[(*b)]; cout << "hej1" << endl; }
    else if ((*a) >= (*_a)) { ans[lo] = ans[(*b)]; cout << "hej2" << endl; }
    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 details

Test 1

Group: 1, 2, 3

Verdict: WRONG ANSWER

input
`1 2 2 1` view save

correct output
(empty)

user output
`IMPOSSIBLE hej2 hej2 IMPOSSIBLE` view save

Test 2

Group: 1, 2, 3

Verdict: WRONG ANSWER

input
`1 3 3 1 2 1` view save

correct output
(empty)

user output
`hej2 hej2 IMPOSSIBLE` view save

Test 3

Group: 1, 2, 3

Verdict: RUNTIME ERROR

input
`1 4 3 2 2 1 4 1` view save

correct output
(empty)

user output
`hej2 hej2` view save

Test 4

Group: 1, 2, 3

Verdict: WRONG ANSWER

input
`1 4 2 3 3 4 1 3` view save

correct output
(empty)

user output
`hej2 IMPOSSIBLE` view save

Test 5

Group: 1, 2, 3

Verdict: RUNTIME ERROR

input
`1 5 3 5 4 1 1 3 ...` view save

correct output
(empty)

user output
`hej2` view save

Test 6

Group: 1, 2, 3

Verdict: WRONG ANSWER

input
`1 5 3 2 3 4 5 1 ...` view save

correct output
(empty)

user output
`hej2 hej2 IMPOSSIBLE` view save

Test 7

Group: 1, 2, 3

Verdict: RUNTIME ERROR

input
`1 5 4 3 1 4 4 2 ...` view save

correct output
(empty)

user output
`hej2` view save

Test 8

Group: 1, 2, 3

Verdict: RUNTIME ERROR

input
`1 10 9 3 8 9 2 9 ...` view save

correct output
(empty)

user output
`hej1 hej2` view save

Test 9

Group: 1, 2, 3

Verdict: WRONG ANSWER

input
`1 10 9 2 5 8 7 1 ...` view save

correct output
(empty)

user output
`hej2 hej2 hej1 hej1 hej2 ...` view save

Test 10

Group: 1, 2, 3

Verdict: RUNTIME ERROR

input
`1 10 10 4 9 1 4 7 ...` view save

correct output
(empty)

user output
(empty)

Test 11

Group: 1, 2, 3

Verdict: RUNTIME ERROR

input
`1 10 2 6 4 3 3 5 ...` view save

correct output
(empty)

user output
`hej2` view save

Test 12

Group: 2, 3

Verdict: RUNTIME ERROR

input
`1 500 10 6 6 255 6 428 ...` view save

correct output
(empty)

user output
`hej2 hej2 hej2` view save

Error:

free(): invalid pointer

Test 13

Group: 2, 3

Verdict: RUNTIME ERROR

input
`1 500 152 466 451 313 158 479 ...` view save

correct output
(empty)

user output
`hej2 hej2 hej2 hej2 hej2 ...` view save

Test 14

Group: 2, 3

Verdict: RUNTIME ERROR

input
`1 500 109 440 330 190 443 161 ...` view save

correct output
(empty)

user output
`hej2 hej2 hej2 hej2 hej2 ...` view save

Test 15

Group: 2, 3

Verdict: RUNTIME ERROR

input
`1 500 144 373 257 233 341 318 ...` view save

correct output
(empty)

user output
`hej2 hej2 hej2 hej2 hej2 ...` view save

Test 16

Group: 3

Verdict: RUNTIME ERROR

input
`1 100000 54983 75172 93807 75172 44082 75172 ...` view save

correct output
(empty)

user output
`hej2 hej2 hej2 hej2 hej2 ...` Truncated

Test 17

Group: 3

Verdict: RUNTIME ERROR

input
`1 100000 88863 19059 86423 76688 98536 95984 ...` view save

correct output
(empty)

user output
`hej2 hej2 hej2 hej2 hej2 ...` Truncated

Test 18

Group: 3

Verdict: RUNTIME ERROR

input
`1 100000 59979 6389 19097 24999 27846 82330 ...` view save

correct output
(empty)

user output
(empty)

Test 19

Group: 3

Verdict: RUNTIME ERROR

input
`1 100000 58761 66001 25102 51081 98625 67861 ...` view save

correct output
(empty)

user output
`hej2 hej2 hej2 hej2 hej2 ...` view save

Test 20

Group: 1, 2, 3

Verdict: WRONG ANSWER

input
`1 6 2 1 3 2 4 2 ...` view save

correct output
(empty)

user output
`hej2 hej2 IMPOSSIBLE` view save

NOI 2019

Distance Code

Code

Test details

Test 1

Test 2

Test 3

Test 4

Test 5

Test 6

Test 7

Test 8

Test 9

Test 10

Test 11

Test 12

Test 13

Test 14

Test 15

Test 16

Test 17

Test 18

Test 19

Test 20

Tasks

Submissions (Hugo Eberhard)