Code Submission Evaluation System Login

HIIT Open 2018

Start:2018-05-26 11:00:00
End:2018-05-26 16:00:00
 

Tasks | Messages | Scoreboard | Statistics


CSES - HIIT Open 2018 - Results
History
2018-05-26 15:31:26
2018-05-26 15:30:31
Task:Monotonic
Sender:Wave of Technology
Submission time:2018-05-26 15:31:26
Language:C++
Status:READY
Result:ACCEPTED

Test results

testverdicttime (s)
#1ACCEPTED0.01 / 2.00details
#2ACCEPTED0.02 / 2.00details
#3ACCEPTED0.02 / 2.00details
#4ACCEPTED0.06 / 2.00details
#5ACCEPTED0.01 / 2.00details
#6ACCEPTED0.01 / 2.00details
#7ACCEPTED0.03 / 2.00details
#8ACCEPTED0.02 / 2.00details
#9ACCEPTED0.02 / 2.00details
#10ACCEPTED0.03 / 2.00details

Code

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<ll, ll> PLL;

const ll INF = 1000000000000000LL;

ll n;

template<typename T>
void print_vector(vector<T> & v) {
  for (auto x : v) {
    cout << x << " ";
  }
}

const ll MAXK = 1000;
const ll TRY = 1000;

ll solve() {
  ll n, m;
  cin >> n >> m;

  vector<PLL> pr(m);
  for (int i=0; i<m; i++) {
    cin >> pr[i].first;
    cin >> pr[i].second;
    pr[i].first--;
    pr[i].second--;
  }

  ll maxk = 0;
  for (int ii=0; ii<TRY; ii++) {
    vector<ll> x (n);
    for (int i=0; i<n; i++) {
      x[i] = rand();
    }

    ll k = 0;
    while (k < MAXK) {
      k++;
      for (auto p : pr) {
	if (x[p.first] > x[p.second]) {
	  swap(x[p.first], x[p.second]);
	}
      }

      bool sorted = true;
      for (int i=0; i<n-1; i++) {
	sorted &= (x[i] <= x[i+1]);
      }

      if (sorted) { break; }
      
    }
    maxk = max(k, maxk);
    if (maxk == MAXK) { break; }
  }

  if (maxk == MAXK) { return -1; } else { return maxk; }
}

int main() {

  cin.tie(NULL);
  std::ios::sync_with_stdio(false);

  ll t;
  cin >> t;
  for (int i=0; i<t; i++) {
    cout << solve() << endl;
  }
  
  return 0;
}

Test details

Test 1

Verdict: ACCEPTED

input
3
4 4
1 2
3 4
1 2
3 4
4 3
1 2
2 3
3 4
2 1
1 2
view   save

correct output
-1
3
1
view   save

user output
-1
3
1
view   save

Test 2

Verdict: ACCEPTED

input
10
15 200
1 14
2 6
3 14
12 13
11 14
5 10
4 10
1 10
3 11
7 11
7 13
12 14
6 9
9 15
8 9
5 15
1 14
1 6
...
view   save

correct output
-1
-1
-1
-1
-1
-1
-1
-1
-1
2
view   save

user output
-1
-1
-1
-1
-1
-1
-1
-1
-1
2
view   save

Test 3

Verdict: ACCEPTED

input
10
15 350
1 14
2 6
3 14
12 13
11 14
5 10
4 10
1 10
3 11
7 11
7 13
12 14
6 9
9 15
8 9
5 15
1 14
1 6
...
view   save

correct output
3
-1
2
-1
1
2
2
2
-1
-1
view   save

user output
3
-1
2
-1
1
2
2
2
-1
-1
view   save

Test 4

Verdict: ACCEPTED

input
10
15 1500
1 14
2 6
3 14
12 13
11 14
5 10
4 10
1 10
3 11
7 11
7 13
12 14
6 9
9 15
8 9
5 15
1 14
1 6
...
view   save

correct output
1
1
1
1
1
1
1
1
1
1
view   save

user output
1
1
1
1
1
1
1
1
1
1
view   save

Test 5

Verdict: ACCEPTED

input
10
15 100
4 10
3 9
6 15
8 10
10 11
2 10
1 15
8 14
5 9
4 12
8 9
9 14
7 8
11 14
3 4
3 11
14 15
7 9
...
view   save

correct output
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
view   save

user output
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
view   save

Test 6

Verdict: ACCEPTED

input
10
15 200
4 5
2 12
7 8
2 3
1 2
7 9
5 15
1 13
4 9
6 9
5 13
3 14
2 5
4 15
1 14
11 13
5 13
4 5
...
view   save

correct output
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
view   save

user output
-1
-1
-1
-1
-1
-1
-1
-1
-1
-1
view   save

Test 7

Verdict: ACCEPTED

input
10
15 300
5 10
6 12
12 13
12 14
11 15
1 9
8 14
4 13
1 11
3 15
2 6
8 14
4 7
2 9
4 10
1 12
4 7
3 5
...
view   save

correct output
-1
-1
2
2
-1
2
-1
2
-1
-1
view   save

user output
-1
-1
2
2
-1
2
-1
2
-1
-1
view   save

Test 8

Verdict: ACCEPTED

input
10
15 400
10 13
2 14
8 13
1 5
1 3
10 11
8 13
6 12
6 13
1 5
8 13
4 12
7 14
9 15
9 11
2 4
9 10
12 13
...
view   save

correct output
-1
1
1
-1
1
2
2
2
1
2
view   save

user output
-1
1
1
-1
1
2
2
2
1
2
view   save

Test 9

Verdict: ACCEPTED

input
10
15 14
14 15
11 12
1 2
13 14
7 8
6 7
4 5
9 10
8 9
12 13
5 6
2 3
10 11
3 4
15 28
3 4
4 5
12 13
...
view   save

correct output
8
7
4
4
3
3
2
2
2
2
view   save

user output
8
7
4
4
3
3
2
2
2
2
view   save

Test 10

Verdict: ACCEPTED

input
10
15 14
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9
9 10
10 11
11 12
12 13
13 14
14 15
15 28
1 2
2 3
3 4
...
view   save

correct output
14
7
5
4
3
3
2
2
2
2
view   save

user output
14
7
5
4
3
3
2
2
2
2
view   save