제출 #47568

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
47568		user202729	Crazy old lady (IZhO13_crazy)	C++17	100 / 100	10 ms	748 KiB

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 / 100