CSES - Siperia opettaa 5.0

CSES - Siperia opettaa 5.0 - Results

Submission details
Task:	Hacker Cups and Balls
Sender:	ollpu
Submission time:	2017-03-09 16:38:55 +0200
Language:	C++
Status:	READY
Result:	0

Feedback
group	verdict	score
#1	WRONG ANSWER	0

Test results
test	verdict	time
#1	ACCEPTED	0.04 s	details
#2	ACCEPTED	0.04 s	details
#3	ACCEPTED	0.05 s	details
#4	ACCEPTED	0.03 s	details
#5	ACCEPTED	0.03 s	details
#6	ACCEPTED	0.04 s	details
#7	ACCEPTED	0.03 s	details
#8	ACCEPTED	0.04 s	details
#9	ACCEPTED	0.03 s	details
#10	ACCEPTED	0.04 s	details
#11	ACCEPTED	0.04 s	details
#12	ACCEPTED	0.04 s	details
#13	WRONG ANSWER	0.19 s	details
#14	WRONG ANSWER	3.33 s	details
#15	TIME LIMIT EXCEEDED	--	details
#16	TIME LIMIT EXCEEDED	--	details
#17	TIME LIMIT EXCEEDED	--	details
#18	TIME LIMIT EXCEEDED	--	details
#19	TIME LIMIT EXCEEDED	--	details
#20	TIME LIMIT EXCEEDED	--	details
#21	TIME LIMIT EXCEEDED	--	details
#22	ACCEPTED	0.22 s	details
#23	TIME LIMIT EXCEEDED	--	details
#24	TIME LIMIT EXCEEDED	--	details
#25	WRONG ANSWER	1.97 s	details
#26	WRONG ANSWER	0.17 s	details

Code

// lol


#include <iostream>
#include <vector>
#include <map>
#include <algorithm>

using namespace std;
#define F first
#define S second

int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  int n, m;
  cin >> n >> m;
  int t[n], sc[n+1];
  map<int, int> srange;
  for (int i = 0; i < n; ++i) {
    cin >> t[i];
    srange[i] = 0;
  }
  int lop = 0;
  pair<int, int> op[m];
  int opt[m];
  for (int i = 0; i < m; ++i) {
    cin >> op[i].F >> op[i].S;
    op[i].F--, op[i].S--;
    if (op[i].F > op[i].S) {
      opt[i] = 1;
      swap(op[i].F, op[i].S);
    } else opt[i] = 0;
    if (op[i].F <= n/2 && op[i].S >= n/2) lop = i+1;
  }
  for (int i = 0; i < lop; ++i) {
    auto it = --srange.upper_bound(op[i].S);
    pair<int, int> asd = *it;
    if (asd.F <= op[i].F) {
      if (asd.S == opt[i]) continue;
      else {
        reverse(t+op[i].F, t+op[i].S+1);
        srange[op[i].S+1] = asd.S;
        srange[op[i].F] = opt[i];
      }
    } else {
      srange.erase(srange.lower_bound(op[i].F), srange.upper_bound(op[i].S));
      srange[op[i].F] = opt[i];
      srange[op[i].S+1] = asd.S;
      if (op[i].S-op[i].F <= 1000) {
        sort(t+op[i].F, t+op[i].S+1);
      } else {
        for (int j = 1; j <= n; ++j) sc[j] = 0;
        for (int j = op[i].F; j <= op[i].S; ++j) {
          sc[t[j]]++;
        }
        int j = op[i].F;
        for (int k = 1; k <= n; ++k) if (sc[j]) t[j++] = k;
      }
      if (opt[i]) reverse(t+op[i].F, t+op[i].S+1);
    }
    // for (int i = 0; i < n; ++i) cout << t[i] << " ";
    // cout << endl;
  }
  cout << t[n/2] << endl;
}

Test details

Test 1

Verdict: ACCEPTED

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

correct output
`2` view save

user output
`2` view save

Test 2

Verdict: ACCEPTED

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

correct output
`4` view save

user output
`4` view save

Test 3

Verdict: ACCEPTED

input
`1 0 1` view save

correct output
`1` view save

user output
`1` view save

Test 4

Verdict: ACCEPTED

input
`1 1 1 1 1` view save

correct output
`1` view save

user output
`1` view save

Test 5

Verdict: ACCEPTED

input
`1 10 1 1 1 1 1 1 1 ...` view save

correct output
`1` view save

user output
`1` view save

Test 6

Verdict: ACCEPTED

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

correct output
`2` view save

user output
`2` view save

Test 7

Verdict: ACCEPTED

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

correct output
`4` view save

user output
`4` view save

Test 8

Verdict: ACCEPTED

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

correct output
`3` view save

user output
`3` view save

Test 9

Verdict: ACCEPTED

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

correct output
`2` view save

user output
`2` view save

Test 10

Verdict: ACCEPTED

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

correct output
`5` view save

user output
`5` view save

Test 11

Verdict: ACCEPTED

input
`99 100 33 54 86 85 32 70 47 59 98 81 ...` view save

correct output
`50` view save

user output
`50` view save

Test 12

Verdict: ACCEPTED

input
`999 1000 403 659 941 361 902 420 562 40...` view save

correct output
`461` view save

user output
`461` view save

Test 13

Verdict: WRONG ANSWER

input
`9999 10000 8825 6550 9856 4921 5469 7019 ...` view save

correct output
`3680` view save

user output
`7628` view save

Test 14

Verdict: WRONG ANSWER

input
`51415 50216 42355 19584 12430 4886 21835 1...` view save

correct output
`42640` view save

user output
`1` view save

Test 15

Verdict: TIME LIMIT EXCEEDED

input
`99999 100000 86561 69211 10709 40653 63761 ...` view save

correct output
`49166` view save

user output
(empty)

Test 16

Verdict: TIME LIMIT EXCEEDED

input
`99999 100000 50393 94271 27420 69389 62906 ...` view save

correct output
`37388` view save

user output
(empty)

Test 17

Verdict: TIME LIMIT EXCEEDED

input
`99999 100000 55963 34569 33638 11733 14583 ...` view save

correct output
`66896` view save

user output
(empty)

Test 18

Verdict: TIME LIMIT EXCEEDED

input
`99999 100000 23085 10457 5546 1569 42452 10...` view save

correct output
`71234` view save

user output
(empty)

Test 19

Verdict: TIME LIMIT EXCEEDED

input
`99999 100000 90828 34481 10990 74758 89452 ...` view save

correct output
`85498` view save

user output
(empty)

Test 20

Verdict: TIME LIMIT EXCEEDED

input
`99999 100000 72770 96635 93330 99517 50465 ...` view save

correct output
`1` view save

user output
(empty)

Test 21

Verdict: TIME LIMIT EXCEEDED

input
`99999 100000 50747 54311 37637 60185 52083 ...` view save

correct output
`99999` view save

user output
(empty)

Test 22

Verdict: ACCEPTED

input
`99999 100000 74605 62077 35821 90758 88963 ...` view save

correct output
`39458` view save

user output
`39458` view save

Test 23

Verdict: TIME LIMIT EXCEEDED

input
`99999 100000 41714 10593 31139 16591 60872 ...` view save

correct output
`50002` view save

user output
(empty)

Test 24

Verdict: TIME LIMIT EXCEEDED

input
`99999 99998 34921 96615 61384 91011 31201 ...` view save

correct output
`20597` view save

user output
(empty)

Test 25

Verdict: WRONG ANSWER

input
`99999 100000 72111 4249 26146 40294 35803 2...` view save

correct output
`50000` view save

user output
`60369` view save

Test 26

Verdict: WRONG ANSWER

input
`99999 100000 28991 50696 14403 60081 49795 ...` view save

correct output
`50000` view save

user output
`43073` view save

Siperia opettaa 5.0

Hacker Cups and Balls

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

Test 21

Test 22

Test 23

Test 24

Test 25

Test 26

Tasks

Submissions (ollpu)