Code Submission Evaluation System Login

CSES - HIIT Open 2018

HIIT Open 2018

Contest start:2018-05-26 11:00:00
Contest end:2018-05-26 16:00:00

Task list | Submit code | Submissions | Messages | Scoreboard | Statistics


History
2018-05-26 15:46:02
2018-05-26 15:02:00
Task:Monotonic
Sender:KnowYourArchitecture
Submission time:2018-05-26 15:46:02
Status:READY
Result:ACCEPTED

Show test data

Code

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef __int128 lll;

constexpr int N = 1000;

mt19937 rnd;
uniform_int_distribution<int> dist(0, 100);

typedef pair<int, int> op;

template<typename T>
void exec(vector<T> &v, vector<op> ops) {
	for (auto o : ops) {
		if (v[o.first] > v[o.second]) {
			swap(v[o.first], v[o.second]);
		}
	}
}

template<typename T>
bool isOrder(const vector<T> &v) {
	for(size_t i = 1; i < v.size(); i++) {
		if (!(v[i-1] <= v[i])) return false;
	}
	return true;
}

inline bool ready(vector<int> &v, int n) {
	int mask = (1 << (n)) - 1;
	for (int a : v) {
		if ((a & mask) != mask) return false;
	}
	return true;
}

void test() {
	int n, m;
	cin >> n >> m;
	vector<int> v(n);
	vector<op> ops(m);
	for (auto &o : ops) {
		cin >> o.first >> o.second;
		o.first--;
		o.second--;
	}
	
	
	// Iterate until ready
	int K = 0;
	for (int t = 0; t < N; t++) {
		// Init v
		for (int i = 0; i < n; i++)
			v[i] = dist(rnd);
		//for (int a:v)cout<<a<<" ";cout<<endl;
		int k = 0;
		while (!isOrder(v) && k++ < 16) {
			exec(v, ops);
		//for (int a:v)cout<<a<<" ";cout<<endl;
		}
		if (k == 17) {
			cout << "-1\n";
			return;
		}
		K = max(k, K);
		
	}
	cout << K << "\n";
}

int main(){
	int t;
	cin>>t;
	while(t--)test();
}