QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#604105#7569. Linesucup-team073RE 1ms5972kbC++203.9kb2024-10-01 23:10:402024-10-01 23:10:41

Judging History

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

  • [2024-10-01 23:10:41]
  • 评测
  • 测评结果:RE
  • 用时:1ms
  • 内存:5972kb
  • [2024-10-01 23:10:40]
  • 提交

answer

#include<bits/stdc++.h>
#ifdef LOCAL
#define debug(...) printf(__VA_ARGS__)
#define edebug(...) fprintf(stderr, __VA_ARGS__)
#else
#define debug(...)
#define edebug(...)
#endif
#define int ll
#define rep(i, x, y) for(int i = x; i <= y; ++i)
#define nrep(i, x, y) for(int i = x; i >= y; --i)
#define ll long long
#define pii std::pair<int,int>
#define pb emplace_back
#define fi first
#define se second
template <class T> 
inline void ckmax(T &a, T b) {
  if(a < b) a = b;
}
template <class T> 
inline void ckmin(T &a, T b) {
  if(a > b) a = b;
}
auto rt_YES = []{puts("YES");};
auto rt_Yes = []{puts("Yes");};
auto rt_NO = []{puts("NO");};
auto rt_No = []{puts("No");};
namespace IO {
#define isdigit(x) (x >= '0' && x <= '9')
  inline char gc() {
    return getchar();
  }
  inline bool blank(char ch) {
    return ch == ' ' || ch == '\n' || ch == '\r' || ch == '\t';
  }
  template <class T>
  inline void read(T &x) {
    double tmp = 1;
    bool sign = 0;
    x = 0;
    char ch = gc();
    for(; !isdigit(ch); ch = gc())
      if(ch == '-') sign = 1;
    for(; isdigit(ch); ch = gc())
      x = x * 10 + (ch - '0');
    if(ch == '.')
      for(ch = gc(); isdigit(ch); ch = gc())
        tmp /= 10.0, x += tmp * (ch - '0');
    if(sign) x = -x;
  }
  inline void read(char *s) {
    char ch = gc();
    for(; blank(ch); ch = gc());
    for(; !blank(ch); ch = gc())
      *s++ = ch;
    *s = 0;
  }
  inline void read(char &c) {
    for(c = gc(); blank(c); c = gc());
  }
  inline void push(const char &c) {
    putchar(c);
  }
  template <class T>
  inline void print(T x) {
    if(x < 0) {
      x = -x;
      push('-');
    }
    static T sta[35];
    T top = 0;
    do {
      sta[top++] = x % 10;
      x /= 10;
    } while(x);
    while(top)
      push(sta[--top] + '0');
  }
  template <class T>
  inline void print(T x, char lastChar) {
    print(x);
    push(lastChar);
  }
}
using namespace IO;

int a[300010];
pii getInterSect(int x,int y){
  // xt+ax = yt+ay
  debug("%lld %lld %lld %lld\n",x,y,a[x],a[y]);
  return{a[y]-a[x],x-y};
}
struct node{
  int id,val,X,Y;
  node(int _id,int _val,int _X,int _Y):
    id(_id),val(_val),X(_X),Y(_Y){}
  bool operator<(node b){return X*b.Y<Y*b.X;}
};
std::vector<node>ans;
int f[300010],v[3];

signed main() {
  clock_t c1 = clock();
#ifdef LOCAL
  freopen("in.in", "r", stdin);
  freopen("out.out", "w", stdout);
#endif
//------------------------------------------------------------------

  int n;read(n);
  rep(i,0,2){
    std::stack<int>s;
    rep(j,0,n){
      read(a[j]);
      if(s.size()<2)s.emplace(j);
      else{
        while(s.size()>=2){
          int S=s.top();s.pop();
          int T=s.top();s.pop();
          pii A=getInterSect(S,j),B=getInterSect(S,T);
          // A.fi/A.se <= B.fi/B.se
          debug("%lld %lld %lld %lld %lld %lld %lld\n",T,S,j,A.fi,A.se,B.fi,B.se);
          if(A.se<0)A.se*=-1,A.fi*=-1;
          if(B.se<0)B.se*=-1,B.fi*=-1;
          if(A.fi*B.se<=A.se*B.fi)s.emplace(T);
          else{s.emplace(T);s.emplace(S);break;}
        }
        s.emplace(j);
      }
    }
    std::vector<int>A;
    while(!s.empty())A.pb(s.top()),s.pop();
    std::reverse(A.begin(),A.end());
    int len=A.size();
    ans.pb(i,0,-1e9,1);
    rep(j,1,len-1){
      pii I=getInterSect(A[j-1],A[j]);
      ans.pb(i,A[j],I.fi,I.se);
      debug("%lld %lld %lld %.2lf\n",i,A[j-1],A[j],I.fi*1.0/I.se);
    }
  }
  std::sort(ans.begin(),ans.end());
  int len=ans.size();
  rep(j,0,len-1){
    auto i=ans[j];
    v[i.id]=i.val;
    if(j!=len-1&&(i.X*ans[j+1].Y==i.Y*ans[j+1].X))continue;
    f[v[0]+v[1]+v[2]]=1;
  }
  std::vector<int>A;
  rep(i,0,n*3)if(!f[i])A.pb(i);
  print(A.size(),'\n');
  for(int i:A)print(i,' ');

//------------------------------------------------------------------
end:
  std::cerr << "Time : " << clock() - c1 << " ms" << std::endl;
  return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 0ms
memory: 5732kb

input:

3
3 1 8 7
9 1 3 1
5 1 1 6

output:

5
1 3 4 7 8 

result:

ok 6 numbers

Test #2:

score: 0
Accepted
time: 1ms
memory: 5672kb

input:

1
1 2
1 2
1 2

output:

2
1 2 

result:

ok 3 number(s): "2 1 2"

Test #3:

score: 0
Accepted
time: 1ms
memory: 5748kb

input:

252
336470888 634074578 642802746 740396295 773386884 579721198 396628655 503722503 971207868 202647942 2087506 268792718 46761498 443917727 16843338 125908043 691952768 717268783 787375312 150414369 693319712 519096230 45277106 856168102 762263554 674936674 407246545 274667941 279198849 527268921 1...

output:

733
4 5 7 9 10 11 12 14 16 17 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 10...

result:

ok 734 numbers

Test #4:

score: 0
Accepted
time: 1ms
memory: 5900kb

input:

96
75475634 804928248 476927808 284875072 503158867 627937890 322595515 786026685 645468307 669240390 939887597 588586447 973764525 521365644 710156469 985188306 860350786 11308832 784695957 770562147 208427221 35937909 67590963 726478310 475357775 255361535 135993561 166967811 46718075 851555000 70...

output:

272
2 4 5 6 7 8 9 10 11 12 13 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 39 40 42 43 44 45 46 47 48 49 50 51 52 53 54 55 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106...

result:

ok 273 numbers

Test #5:

score: 0
Accepted
time: 0ms
memory: 5972kb

input:

237
374288891 535590429 751244358 124321145 232930851 266089174 543529670 773363571 319728747 580543238 582720391 468188689 490702144 598813561 138628383 284660056 733781508 155605777 931759705 245485733 723534730 257812292 794937524 596788519 188451996 981010588 14483682 59267682 959461493 32106527...

output:

685
2 5 6 7 8 9 10 11 12 13 14 15 17 18 19 20 21 22 23 24 26 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 44 45 46 47 48 49 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 106 107 108 ...

result:

ok 686 numbers

Test #6:

score: -100
Runtime Error

input:

213081
673102149 561219907 730593611 814024114 812959730 314305867 469496529 350635050 699021890 342102981 815487777 787982418 857896659 526518374 421876106 438907614 902179526 449645826 783856158 865633510 238642240 774653971 962475573 467098727 196513513 561435449 333165290 951567552 726980720 645...

output:


result: