QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#104807#6395. Equation Discoveringgapinho#RE 15ms43556kbC++203.3kb2023-05-12 00:14:312023-05-12 00:14:31

Judging History

你现在查看的是最新测评结果

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2023-05-12 00:14:31]
  • 评测
  • 测评结果:RE
  • 用时:15ms
  • 内存:43556kb
  • [2023-05-12 00:14:31]
  • 提交

answer

#include <bits/stdc++.h>
using namespace std;

using ll = __int128_t;

#define int long long

using ii = pair<int, int>;

// #define endl '\n'

const int ms = 1e6;
const int mod = 998244353;
const double eps = 2e-3;

int l[ms], r[ms];
string op[ms];
int lo[10], hi[10];
double dp[23][ms];
bool poss[23][ms];
int z = 1;
double val[23];
double expe[23];

int cmp(double a, double b) {
  if(abs(a-b)/max(1.0, abs(b)) <= eps) return 0;
  if(a < b) return -1;
  if(a > b) return 1;
}

void calc(int id, int u) {
  poss[id][u] = 1;
  if(op[u] == "x") {
    dp[id][u] = val[id];
    return;
  }
  if(!poss[id][l[u]]) {
    poss[id][u] = 0;
    return;
  }
  if(op[u] == "sin") {
    dp[id][u] = sin(dp[id][l[u]]);
    return;
  } 
  if(op[u] == "cos") {
    dp[id][u] = cos(dp[id][l[u]]);
    return;
  }
  if(!poss[id][r[u]]) {
    poss[id][u] = 0;
    return;
  }
  double x = dp[id][l[u]];
  double y = dp[id][r[u]];
  if(op[u] == "+") {
    dp[id][u] = x+y;
  } else if(op[u] == "*") {
    dp[id][u] = x*y;
  } else if(op[u] == "-") {
    dp[id][u] = x-y;
  } else {
    if(y < 0.0105) {
      poss[id][u] = 0;
    } else dp[id][u] = x/y;
  }
}

void printtree(int u) {
  if(op[u] == "x") {
    cout << op[u];
  } else if(op[u] == "sin" || op[u] == "cos") {
    cout << op[u] << "(";
    printtree(l[u]);
    cout << ")";
  } else {
    cout << "(";
    printtree(l[u]);
    cout << op[u];
    printtree(r[u]);
    cout << ")";
  }
}

void solve() {
  op[0] = "x";
  lo[0] = 0;
  hi[0] = 1;
  for(int i = 1; i <= 9; i++) {
    lo[i] = z;
    for(int x = lo[i-1]; x < hi[i-1]; x++) {
      l[z] = x;
      op[z] = "sin";
      z++;
      l[z] = x;
      op[z] = "cos";
      z++;
    }
    for(int j = 0; j <= i-2; j++) {
      int k = i-2-j;
      for(int x = lo[j]; x < hi[j]; x++) {
        for(int y  = lo[k]; y < hi[k]; y++) {
          l[z] = x;
          r[z] = y;
          op[z] = "+";
          z++;
          l[z] = x;
          r[z] = y;
          op[z] = "-";
          z++;
          l[z] = x;
          r[z] = y;
          op[z] = "*";
          z++;
          l[z] = x;
          r[z] = y;
          op[z] = "/";
          z++;
        }
      }
    }
    hi[i] = z;
  }
  int n;
  cin >> n;
  // printtree(n);
  // return;
  // printtree(2);
  // cout << endl;
  for(int i = 0; i < n; i++) {
    cin >> val[i] >> expe[i];
  }
  for(int j = 0; j < z; j++) {
    bool valid = true;
    for(int i = 0; i < n; i++) {
      calc(i, j);
      if(!poss[i][j] || cmp(dp[i][j], expe[i]) != 0) {
        valid = false;
      }
    }
    if(valid) {
      printtree(j);
      cout << endl;
      return;
      // break;
    }
  }
  // cout << dp[0][2] << endl;
  // cout << dp[1][2] << endl;
  // cout << dp[2][2] << endl;
  // cout << sin(0.61800) << endl;
  // cout << dp[0][l[630]] << endl;
  // cout << dp[0][l[l[630]]] << endl;
  // for(int i = 0; i < n; i++) {
  //   cout << dp[i][630] << " ?? " << poss[i][630] << endl;
  // }
  assert(false);
}

int32_t main() {
    cin.tie(0); ios::sync_with_stdio(0);
    cout << fixed << setprecision(9);
    int testes = 1;
    // cin >> testes;
    int test = 0;

    while(testes--) {
      // cout << "Case #" << (++test) << ": ";
        solve();
    }
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 15ms
memory: 43556kb

input:

3
1.000000 1.000000
2.000000 4.000000
3.000000 9.000000

output:

(x*x)

result:

ok great!!

Test #2:

score: 0
Accepted
time: 4ms
memory: 42496kb

input:

3
0.618000 1.517072
0.314000 3.132637
1.414000 0.494016

output:

(sin(x)/(x*x))

result:

ok great!!

Test #3:

score: 0
Accepted
time: 10ms
memory: 41948kb

input:

5
77.685777 233.057331
-66.445083 -199.335249
79.966717 239.900151
84.982130 254.946390
-31.528900 -94.586700

output:

(x+(x+x))

result:

ok great!!

Test #4:

score: -100
Dangerous Syscalls

input:

5
25.032427 -0.100652
38.727324 1.658518
27.684334 -0.669555
64.282391 8.275303
52.640700 -0.962660

output:


result: