Submission #47568

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
47568	2018-05-05T04:05:22 Z	user202729	Crazy old lady (IZhO13_crazy)	C++17	100 / 100	10 ms	748 KB

crazy

// https://oj.uz/problem/view/IZhO13_crazy
#include<iostream>
#include<vector>

int main(){
	std::ios::sync_with_stdio(0);std::cin.tie(0);

	std::vector<int> seat;
	std::vector<char> occupied;
	int ntest;std::cin>>ntest;while(ntest-->0){
		int n;std::cin>>n;
		seat.resize(n);
		for(int& s:seat)std::cin>>s,--s;
		if(n==1){std::cout<<"1\n";continue;}

		int candidate=-1;
		for(int c=n;c-->0;){
			// check if ocr orig seat can be c
			bool possible=true;
			occupied.assign(n,false);
			occupied[seat[0]]=true;

			for(int index=1,s=0==c;s<n;++s,s+=s==c,++index){
				// passenger (index) is assigned to seat (s)
				if(occupied[s]){
					if(seat[index]==s){possible=false;break;} // this should not happen
					occupied[seat[index]]=true;
				}else{
					if(seat[index]!=s){possible=false;break;}
					occupied[s]=true;
				}
			}

			if(possible){
				if(candidate>=0){
					candidate=-1;break; // cannot determine, multiple answer
				}else{
					candidate=c;
				}
			}

		} // note that if the ocr happen to choose her own seat then candidate is -1 as well
		std::cout<<1+candidate<<'\n';
	}
}

Subtask #1

100.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	376 KB	Output is correct
2	Correct	2 ms	376 KB	Output is correct
3	Correct	2 ms	544 KB	Output is correct
4	Correct	2 ms	544 KB	Output is correct
5	Correct	2 ms	544 KB	Output is correct
6	Correct	2 ms	544 KB	Output is correct
7	Correct	2 ms	584 KB	Output is correct
8	Correct	2 ms	596 KB	Output is correct
9	Correct	3 ms	620 KB	Output is correct
10	Correct	4 ms	620 KB	Output is correct
11	Correct	3 ms	636 KB	Output is correct
12	Correct	4 ms	748 KB	Output is correct
13	Correct	3 ms	748 KB	Output is correct
14	Correct	4 ms	748 KB	Output is correct
15	Correct	7 ms	748 KB	Output is correct
16	Correct	6 ms	748 KB	Output is correct
17	Correct	6 ms	748 KB	Output is correct
18	Correct	10 ms	748 KB	Output is correct
19	Correct	8 ms	748 KB	Output is correct
20	Correct	10 ms	748 KB	Output is correct