oj.uz

Submission #296364

# Submission time Handle Problem Language Result Execution time Memory
296364 2020-09-10T13:54:50 Z BThero Park (JOI17_park) C++17
20 / 100
 104 ms 632 KB 
// chrono::system_clock::now().time_since_epoch().count()
#include "park.h"
#include<bits/stdc++.h>

#define pb push_back
#define eb emplace_back
#define mp make_pair
#define fi first
#define se second
#define all(x) (x).begin(), (x).end()
#define debug(x) cerr << #x << " = " << x << endl;

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;

namespace {
  int subtask_no, n;
  mt19937 rnd(chrono::system_clock::now().time_since_epoch().count());
  
  bool ask(int a, int b, vector<int> &vec) {
    if (a > b) {
      swap(a, b);
    }
  
    int tmp[n];
    fill(tmp, tmp + n, 0);
    
    for (int x : vec) {
      tmp[x] = 1;
    }
    
    return Ask(a, b, tmp);
  }
  
  void report(int a, int b) {
    if (a > b) {
      swap(a, b);
    }
  
    Answer(a, b);
  }
  
  vector<int> calc(int L, int R, vector<int> S) {
    vector<int> ret;
    
    if (S.size() == 2) {
      ret.pb(L);
      ret.pb(R);
      return ret;
    }
    
    int m = rnd() % S.size();
    
    while (S[m] == L || S[m] == R) {
      m = rnd() % S.size();
    }
    
    int M = S[m];
    vector<int> A, B;
    A.pb(L);
    A.pb(M);
    B.pb(M);
    B.pb(R);
    
    for (int x : S) {
      if (x != L && x != M && x != R) {
        vector<int> S2 = S;
        S2.erase(find(all(S2), x));
      
        if (ask(L, M, S2)) {
          B.pb(x);
        }
        else {
          A.pb(x);
        }
      }
    }
    
    A = calc(L, M, A);
    B = calc(M, R, B);
    
    for (int x : A) {
      ret.pb(x);
    }
    
    ret.pop_back();
    
    for (int x : B) {
      ret.pb(x);
    }
    
    return ret;
  }
  
  void solve() {
    if (subtask_no == 2) {  
      vector<int> S;
      
      for (int i = 0; i < n; ++i) {
        S.pb(i);
      }
      
      S = calc(0, n - 1, S);
      
      for (int i = 0; i + 1 < n; ++i) {
        report(S[i], S[i + 1]);
      }
    }
    else {
      for (int i = 0; i < n; ++i) {
        for (int j = i + 1; j < n; ++j) {
          vector<int> S;
          S.pb(i);
          S.pb(j);
          
          if (ask(i, j, S)) {
            report(i, j);
          }
        }
      }
    }
  }
};

void Detect(int T, int N) {
  subtask_no = T;
  n = N;
  solve();
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 384 KB Output is correct
2 Correct 16 ms 384 KB Output is correct
3 Correct 16 ms 384 KB Output is correct
4 Correct 16 ms 384 KB Output is correct
5 Correct 17 ms 384 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 103 ms 512 KB Output is correct
2 Correct 69 ms 512 KB Output is correct
3 Correct 93 ms 632 KB Output is correct
4 Correct 102 ms 632 KB Output is correct
5 Correct 104 ms 512 KB Output is correct

Subtask #3
0 / 27.0

# Verdict Execution time Memory Grader output
1 Incorrect 98 ms 512 KB Wrong Answer[5]
2 Halted 0 ms 0 KB -

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 74 ms 504 KB Wrong Answer[5]
2 Halted 0 ms 0 KB -

Subtask #5
0 / 23.0

# Verdict Execution time Memory Grader output
1 Incorrect 99 ms 384 KB Wrong Answer[5]
2 Halted 0 ms 0 KB -