oj.uz

Submission #658611

# Submission time Handle Problem Language Result Execution time Memory
658611 2022-11-13T18:51:59 Z Dec0Dedd Meandian (CEOI06_meandian) C++14
100 / 100
 9 ms 208 KB 
#include <bits/stdc++.h>
#include "libmean.h"

using namespace std;

#define pii pair<int, int>

int n;

int ask(int *a) {
   return Meandian(a[0], a[1], a[2], a[3]);
}

bool bad(int c, int *a) {
   int i=-1, j=-1, x=-1, y=-1;
   for (int p=0; p<3; ++p) {
      if (a[p] == c) continue;
      if (i == -1) i=a[p];
      else j=a[p];
   }

   for (int p=1; p<=n; ++p) {
      if (p == i || p == c || p == j) continue;
      if (x == -1) x=p;
      else y=p;
   }
   
   int b[4]={i, j, x, y};
   int tmp=ask(b), iv, jv;
   b[0]=c; jv=ask(b);
   b[1]=i; iv=ask(b);

   if (tmp == iv || tmp == jv) return false;
   return true;
}

pair<int, int> findEx(bool mv) {
   int a[4] = {1, 2, 3, 4}, mn=ask(a);
   for (int i=5; i<=n; ++i) {
      int rm=-1;

      for (int j=0; j<4; ++j) {
         int tmp=a[j]; a[j]=i;
         int x=ask(a);
         a[j]=tmp;

         if (mv && x < mn) rm=j, mn=x;
         else if (!mv && x > mn) rm=j, mn=x;
      }

      if (rm != -1) a[rm]=i;
   } mn=ask(a);

   int x=-1;
   for (int i=1; i<=n; ++i) {
      bool ok=true;
      for (int j=0; j<4; ++j) {
         if (i == a[j]) {
            ok=false;
            break;
         }
      }

      if (!ok) continue;
      x=i;
   }

   // remove most external element
   for (int i=0; i<4; ++i) {
      int tmp[4]={};
      for (int j=0; j<4; ++j) {
         if (i == j) continue;
         tmp[j]=a[j];
      } tmp[i]=x;

      if (mn == ask(tmp)) {
         a[i]=-1;
         break;
      }
   }

   vector<int> v;
   for (int i=0; i<4; ++i) {
      if (a[i] == -1) continue;
      v.push_back(a[i]);
   } assert((int)v.size() == 3);

   int b[3];
   for (int i=0; i<3; ++i) b[i]=v[i];

   for (int i=0; i<3; ++i) {
      if (bad(b[i], b)) {
         if (i == 0) return {b[1], b[2]};
         else if (i == 1) return {b[0], b[2]};
         return {b[0], b[1]};
      }
   } assert(false);

   return {-1, -1};
}

int main() {
   ios_base::sync_with_stdio(0);
   cin.tie(NULL);
   cout.tie(NULL);

   n=Init();
   pii mn=findEx(true);
   pii mx=findEx(false);

   int ans[n]={}, idx=-1, val=-1;

   for (int i=1; i<=n; ++i) {
      if (i == mn.first || i == mn.second) continue;
      if (i == mx.first || i == mx.second) continue;
      idx=i;
      break;
   }

   int a[4]={mn.first, mn.second, idx, mx.first};
   int lf=ask(a)*2, rf, wth;
   a[0]=mx.second; rf=ask(a)*2;
   a[2]=mn.first; wth=ask(a)*2;
   val=(lf+rf-wth)/2; assert((lf+rf-wth)%2 == 0);
   ans[idx-1]=val;

   assert(idx != -1);
   for (int i=1; i<=n; ++i) {
      if (i == mn.first || i == mn.second || i == mx.first || i == mx.second) {
         ans[i-1]=-1;
         continue;
      }

      if (i == idx) continue;
      int a[4]={mn.first, idx, i, mx.first};
      int p=ask(a)*2; ans[i-1]=p-val;
   }
   Solution(ans);
}

Subtask #1
100.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 208 KB Output is correct
2 Correct 1 ms 208 KB Output is correct
3 Correct 1 ms 208 KB Output is correct
4 Correct 2 ms 208 KB Output is correct
5 Correct 2 ms 208 KB Output is correct
6 Correct 3 ms 208 KB Output is correct
7 Correct 4 ms 208 KB Output is correct
8 Correct 6 ms 208 KB Output is correct
9 Correct 9 ms 208 KB Output is correct
10 Correct 9 ms 208 KB Output is correct