CSES - KILO 2015 2/5

Submission details
Task:	Interview
Sender:	infosec
Submission time:	2015-09-16 17:53:54 +0300
Language:	C++
Status:	READY
Result:	ACCEPTED

Test results
test	verdict	time
#1	ACCEPTED	0.05 s	details
#2	ACCEPTED	0.05 s	details
#3	ACCEPTED	0.05 s	details
#4	ACCEPTED	0.05 s	details
#5	ACCEPTED	0.10 s	details
#6	ACCEPTED	0.10 s	details
#7	ACCEPTED	0.10 s	details
#8	ACCEPTED	0.10 s	details
#9	ACCEPTED	0.09 s	details
#10	ACCEPTED	0.10 s	details
#11	ACCEPTED	0.11 s	details
#12	ACCEPTED	0.10 s	details
#13	ACCEPTED	0.10 s	details
#14	ACCEPTED	0.10 s	details
#15	ACCEPTED	0.10 s	details
#16	ACCEPTED	0.10 s	details
#17	ACCEPTED	0.10 s	details
#18	ACCEPTED	0.06 s	details
#19	ACCEPTED	0.05 s	details
#20	ACCEPTED	0.05 s	details
#21	ACCEPTED	0.05 s	details
#22	ACCEPTED	0.05 s	details
#23	ACCEPTED	0.05 s	details
#24	ACCEPTED	0.05 s	details
#25	ACCEPTED	0.05 s	details
#26	ACCEPTED	0.05 s	details
#27	ACCEPTED	0.06 s	details
#28	ACCEPTED	0.07 s	details
#29	ACCEPTED	0.05 s	details
#30	ACCEPTED	0.05 s	details
#31	ACCEPTED	0.06 s	details
#32	ACCEPTED	0.05 s	details
#33	ACCEPTED	0.06 s	details
#34	ACCEPTED	0.07 s	details
#35	ACCEPTED	0.07 s	details
#36	ACCEPTED	0.07 s	details
#37	ACCEPTED	0.10 s	details

Code

#include <iostream>
#include <fstream>
#include <sstream>
#include <algorithm>
#include <queue>
#include <stack>
#include <vector>
#include <map>
#include <math.h> 

#define FILE_INP "interview.inp"
#define MAXN 150000
#define MAXVAL 1000000001

using namespace std;

int n;
int a[MAXN];
int res;

void read(istream &fin) 
{
	int h;
	n = 1;

	fin >> h; 
	n = pow(2, h);

	for (int i = 0; i < n; i++) {
		fin >> a[i];
	}
}

bool process(int l, int r) 
{
	if (l >= r) {
		return true;
	}
	int mid = (l+r)/2;
	if (process(l, mid) == false || process(mid+1, r) == false) {
		return false;
	}
	int min1 = MAXVAL;
	int min2 = MAXVAL;
	int max1 = 0;
	int max2 = 0;
	for (int i = l; i <= mid; i++) {
		if (a[i] < min1) {
			min1 = a[i];
		}
		if (a[i] > max1) {
			max1 = a[i];
		}
	}

	for (int i = mid+1; i <= r; i++) {
		if (a[i] < min2) {
			min2 = a[i];
		}
		if (a[i] > max2) {
			max2 = a[i];
		}
	}
	if (max1 <= min2) {
		return true;
	} else if (max2 <= min1) {
		res ++;
		int gap = (r-l)/2 + 1;
		for (int i = l; i <= mid; i++) {
			swap(a[i], a[i+gap]);
		}
		return true;
	} else {
		return false;
	}
	// cout << l << " " << mid << " " << r << endl;
}

int main()
{
    // ifstream fin(FILE_INP);
    // read(fin);
    read(cin);
    
    res = 0;
    if (n > 1) {
    	if (process(0, n-1) == false) {
    		res = -1;
    	}
    } 
    
    if (res == -1) {
    	cout << "QAQ";
    } else {
    	cout << res;
    }

    // fin.close();
    return 0;
}

Test details

Test 1

Verdict: ACCEPTED

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

correct output
`2` view save

user output
`2` view save

Test 2

Verdict: ACCEPTED

input
`2 1000 100 10 1` view save

correct output
`3` view save

user output
`3` view save

Test 3

Verdict: ACCEPTED

input
`2 1 4 2 3` view save

correct output
`QAQ` view save

user output
`QAQ` view save

Test 4

Verdict: ACCEPTED

input
`4 38 48 31 29 9 2 25 23 60 63 67...` view save

correct output
`7` view save

user output
`7` view save

Test 5

Verdict: ACCEPTED

input
`17 125327615 125311457 125338848 ...` view save

correct output
`58869` view save

user output
`58869` view save

Test 6

Verdict: ACCEPTED

input
`17 528159436 528155011 528165801 ...` view save

correct output
`70714` view save

user output
`70714` view save

Test 7

Verdict: ACCEPTED

input
`17 514083812 514081465 514080093 ...` view save

correct output
`82479` view save

user output
`82479` view save

Test 8

Verdict: ACCEPTED

input
`17 642975535 642974649 642980533 ...` view save

correct output
`94267` view save

user output
`94267` view save

Test 9

Verdict: ACCEPTED

input
`17 999999983 999999983 999999983 ...` view save

correct output
`352` view save

user output
`352` view save

Test 10

Verdict: ACCEPTED

input
`17 999999965 999999965 999999965 ...` view save

correct output
`265` view save

user output
`265` view save

Test 11

Verdict: ACCEPTED

input
`17 999999951 999999951 999999951 ...` view save

correct output
`202` view save

user output
`202` view save

Test 12

Verdict: ACCEPTED

input
`17 999999989 999999989 999999989 ...` view save

correct output
`135` view save

user output
`135` view save

Test 13

Verdict: ACCEPTED

input
`17 999999950 999999950 999999950 ...` view save

correct output
`58` view save

user output
`58` view save

Test 14

Verdict: ACCEPTED

input
`17 999999994 999999994 999999994 ...` view save

correct output
`96` view save

user output
`96` view save

Test 15

Verdict: ACCEPTED

input
`17 999999993 999999993 999999993 ...` view save

correct output
`70` view save

user output
`70` view save

Test 16

Verdict: ACCEPTED

input
`17 999999991 999999991 999999991 ...` view save

correct output
`44` view save

user output
`44` view save

Test 17

Verdict: ACCEPTED

input
`17 999999990 999999990 999999990 ...` view save

correct output
`14` view save

user output
`14` view save

Test 18

Verdict: ACCEPTED

input
`0 7` view save

correct output
`0` view save

user output
`0` view save

Test 19

Verdict: ACCEPTED

input
`1 8 63` view save

correct output
`0` view save

user output
`0` view save

Test 20

Verdict: ACCEPTED

input
`2 45 34 61 72` view save

correct output
`1` view save

user output
`1` view save

Test 21

Verdict: ACCEPTED

input
`3 21 27 66 68 81 73 91 95` view save

correct output
`1` view save

user output
`1` view save

Test 22

Verdict: ACCEPTED

input
`4 9 2 20 25 28 26 49 39 74 58 50...` view save

correct output
`7` view save

user output
`7` view save

Test 23

Verdict: ACCEPTED

input
`5 32 27 36 34 42 49 38 39 4 5 9 ...` view save

correct output
`11` view save

user output
`11` view save

Test 24

Verdict: ACCEPTED

input
`6 71 70 66 70 64 65 62 62 59 59 ...` view save

correct output
`28` view save

user output
`28` view save

Test 25

Verdict: ACCEPTED

input
`7 16 14 17 19 22 22 20 20 23 23 ...` view save

correct output
`30` view save

user output
`30` view save

Test 26

Verdict: ACCEPTED

input
`8 78 78 76 76 78 78 78 78 82 83 ...` view save

correct output
`73` view save

user output
`73` view save

Test 27

Verdict: ACCEPTED

input
`9 3 3 4 4 4 4 4 4 6 6 6 6 5 5 5 ...` view save

correct output
`84` view save

user output
`84` view save

Test 28

Verdict: ACCEPTED

input
`10 28 28 28 28 28 28 28 28 28 29 ...` view save

correct output
`119` view save

user output
`119` view save

Test 29

Verdict: ACCEPTED

input
`11 93 93 93 93 93 93 93 93 93 93 ...` view save

correct output
`161` view save

user output
`161` view save

Test 30

Verdict: ACCEPTED

input
`12 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 ...` view save

correct output
`192` view save

user output
`192` view save

Test 31

Verdict: ACCEPTED

input
`13 21 21 21 21 21 21 21 21 21 21 ...` view save

correct output
`260` view save

user output
`260` view save

Test 32

Verdict: ACCEPTED

input
`14 13 13 13 13 13 13 13 13 13 13 ...` view save

correct output
`303` view save

user output
`303` view save

Test 33

Verdict: ACCEPTED

input
`15 90 90 90 90 90 90 90 90 90 90 ...` view save

correct output
`332` view save

user output
`332` view save

Test 34

Verdict: ACCEPTED

input
`16 37 37 37 37 37 37 37 37 37 37 ...` view save

correct output
`354` view save

user output
`354` view save

Test 35

Verdict: ACCEPTED

input
`17 10 10 10 10 10 10 10 10 10 10 ...` view save

correct output
`399` view save

user output
`399` view save

Test 36

Verdict: ACCEPTED

input
`17 30 30 30 30 30 30 30 30 30 30 ...` view save

correct output
`QAQ` view save

user output
`QAQ` view save

Test 37

Verdict: ACCEPTED

input
`17 530333517 530335373 530344723 ...` view save

correct output
`QAQ` view save

user output
`QAQ` view save

KILO 2015 2/5

Interview

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

Test 27

Test 28

Test 29

Test 30

Test 31

Test 32

Test 33

Test 34

Test 35

Test 36

Test 37

Tasks

Submissions (infosec)