记录详情

Time Exceeded

/in/foo.cc: In function 'int read()':
/in/foo.cc:8:30: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
  while(ch>'9'||ch<'0')ch=='-'&&(f=0)||(ch=getchar());
                       ~~~~~~~^~~~~~~
# 状态 耗时 内存占用
#1 Accepted 91ms 26.301 MiB
#2 Time Exceeded ≥1000ms ≥26.172 MiB
#3 Accepted 80ms 20.199 MiB
#4 Accepted 76ms 18.199 MiB
#5 Accepted 486ms 26.203 MiB
#6 Accepted 773ms 26.297 MiB
#7 Accepted 663ms 26.297 MiB
#8 Accepted 208ms 26.301 MiB
#9 Accepted 126ms 26.297 MiB
#10 Accepted 998ms 26.297 MiB

代码

#pragma GCC optimize(2)

#include <bits/stdc++.h>
#define N 2000020
using namespace std;
inline int read(){
	int x=0,f=1;char ch=getchar();
	while(ch>'9'||ch<'0')ch=='-'&&(f=0)||(ch=getchar());
	while(ch<='9'&&ch>='0')x=(x<<3)+(x<<1)+ch-'0',ch=getchar();
	return f?x:-x;
}

int pri[N], mark[N], p[N], cnt;

void shai(int n) {
  for (int i = 2; i <= n; ++ i) {
    if (!mark[i]) pri[++ cnt] = i, p[i] = i;
    for (int j = 1; j <= cnt && i * pri[j] <= n; ++ j) {
      mark[i * pri[j]] = 1;
      p[i * pri[j]] = pri[j];
    }
  }
}

int a[N], tot, bs[N], totb, cs[N];

void chai(int x) {
  while (x > 1) {
    int ps = p[x];
    x /= ps;
    a[++ tot] = ps;
  }
}

long long MAX_DFS = 0, damn;
int ans = 0, res = 0;
long long fuck[N], bbs[N];

int A;
double srt;

void dfs(int d, long long val) {
  if (val > MAX_DFS) return;
  if (d > totb) {
    if (val < A) return;
    int cpb = val;
    int cmb = damn / cpb;
    if ((cmb + cpb) & 1) {
      return;
    }
    int c = (cpb + cmb) >> 1;
    int b = (cpb - cmb) >> 1;
    if (b < A) {
      return;
    }
    ++ ans;
    res ^= (A + b) ^ c;
    // printf("Found %d %d %d\n", A, b, c);
    return;
  }
  if (val * fuck[d] < A) return;
  for (int i = 0; i <= cs[d]; ++ i) {
    dfs(d + 1, val);
    val = val * bs[d];
  }
}

int main() {
  int n = read();
  shai(2000001);
int sss=n-sqrt(((long long)n*n+1)/2);
  for (A = 2; A <= sss; ++ A) {
    // (a-1)(a+1) = (c-b)(c+b)
    damn = (long long) A * A - 1;
    tot = 0;
    chai(A - 1);
    chai(A + 1);
    MAX_DFS = n - A;
    sort(a + 1, a + tot + 1);
    totb = 0;
    for (int i = 1; i <= tot; ++ i) {
      if (a[i] != a[i - 1]) {
        bs[++ totb] = a[i];
        cs[totb] = 1;
        bbs[totb] = a[i];
      } else {
        cs[totb] ++;
        bbs[totb] *= a[i];
      }
    }
    fuck[totb + 1] = 1;
    for (int i = totb; i; -- i) {
      fuck[i] = fuck[i + 1] * bbs[i];
    }

    // if (A == 1651) {
    //   for (int i = 1; i <= totb; ++ i) {
    //     printf("%d %d %lld %lld\n", bs[i], cs[i], bbs[i], fuck[i]);
    //   }
    //   return 0;
    // }

    dfs(1, 1);
  }
  for (int i = 1; 2*i+1 <= n; ++ i) {
    ++ ans;
    res ^= (i + 1) ^ i;
  }
  printf("%d %d\n", ans, res);
}

信息

递交者
类型
递交
题目
P1003 hitwh 2019 新生赛 D Songer 的排兵布阵
语言
C++
递交时间
2020-12-17 17:13:35
评测时间
2020-12-17 17:13:35
评测机
分数
90
总耗时
≥4506ms
峰值内存
≥26.301 MiB