oj.uz

답안 #295237

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
295237 2020-09-09T14:36:04 Z erd1 송금 (JOI19_remittance) C++14
55 / 100
 288 ms 16856 KB 
#include<bits/stdc++.h>
#define int lld
#define ff first
#define ss second
#define pb push_back
#define all(x) (x).begin(), (x).end()
using namespace std;
typedef int64_t lld;
typedef pair<int, int> pii;

template<int MOD, int H>
struct S{
  inline static int mdu(int a){ return a < 0?a+MOD:a; }
  inline static int mdd(int a){ return a>=MOD?a-MOD:a; }
  inline static int d2(int a){ return a&1?mdd((a>>1)+H):(a>>1); }
  static int invmod(int a, int b = MOD, int s0 = 0, int s1 = 1){
    return b?invmod(b, a%b, mdu(s1-(lld)(a/b)*s0%MOD), s0):s1;
  }
  int f, s;
  S(int a){ f = 0, s = a; }
  S(int a, int b){ f = a, s = b; }
  S operator+(S a){ return {mdd(f+a.f), mdd(s+a.s)}; }
  S operator-(S a){ return {mdu(f-a.f), mdu(s-a.s)}; }
  S d2(){ assert(f >= 0 && f < MOD); assert(s >= 0 && s < MOD); return {d2(f), d2(s)}; }
  friend ostream& operator<<(ostream& out, S a){ return out << a.f << "x + " << a.s; }
  int solve(){ return (lld)s*invmod(mdu(1-f))%MOD; }
};

const int md1 = 1000000007, md2 = 1000000009, h1 = 500000004, h2 = 500000005;

vector<pii> v;
signed main(){ ios::sync_with_stdio(0); cin.tie(0);
  int n;
  cin >> n;
  S<md1, h1> curgive1 = {1, 0};
  S<md2, h2> curgive2 = {1, 0};
  //S<md3> curgive3 = {1, 0};
  lld suma = 0, sumb = 0;
  for(int i = 0; i < n; i++){
    int a, b;
    cin >> a >> b;
    v.pb({a, b});
    suma += a, sumb += b;
    curgive1 = (curgive1+a-b).d2();
    curgive2 = (curgive2+a-b).d2();
    //curgive3 = (curgive3+a-b)/2;
    //cout << curgive1 << endl << curgive2 << endl;
    //cout << curgive1.solve() << " " << curgive2.solve() << endl;
  }
  if(!sumb && suma)return cout << "No" << endl, 0;
  assert((curgive1.f != 1) && (curgive2.f != 1));
  if(curgive1.f == 1){
    return cout << "Yes" << endl, 0;
  }
  if(n > 20) exit(0);
  lld ans;
  /*
  if(curgive1.f == 1){
    if(curgive2.f == 1 || curgive3.f == 1)return cout << "No" << endl, 0;
    lld ans3 = curgive3.solve(), ans2 = curgive2.solve(); // a = ((lld)(ans2-ans1)*invmod(md1, md2)%md2+md2)%md2 (mod md2)
    ans = (lld)S<md2>::mdu((ans2-ans3)*S<md2>::invmod(md3)%md2)*md3+ans3;
  } else if(curgive2.f == 1) {
    lld ans1 = curgive1.solve(), ans3 = curgive3.solve(); // a = ((lld)(ans2-ans1)*invmod(md1, md2)%md2+md2)%md2 (mod md2)
    ans = (lld)S<md3>::mdu((ans3-ans1)*S<md3>::invmod(md1)%md3)*md1+ans1;
  } else if(curgive3.f == 1)
    return cout << "No" << endl, 0;
  else*/ {
    lld ans1 = curgive1.solve(), ans2 = curgive2.solve(); // a = ((lld)(ans2-ans1)*invmod(md1, md2)%md2+md2)%md2 (mod md2)
    ans = (lld)S<md2, h2>::mdu((ans2-ans1)*S<md2, h2>::invmod(md1)%md2)*md1+ans1;
    assert(ans%md1 == ans1 && ans%md2 == ans2);
  }
  //cout << ans << endl;
  lld curgive = ans;
  for(int i = 0; i < n; i++){
    curgive = curgive + v[i].ff-v[i].ss;
    //cout << curgive << endl;
    if(curgive<0 || (curgive&1))return cout << "No" << endl, 0;
    curgive /= 2;
  }
  if(curgive == ans)cout << "Yes" << endl;
  else cout << "No" << endl;
}
/*
5
0 0
1 0
2 3
3 3
4 0
*/

Subtask #1
15.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 0 ms 384 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 0 ms 384 KB Output is correct
6 Correct 0 ms 384 KB Output is correct
7 Correct 0 ms 384 KB Output is correct
8 Correct 0 ms 384 KB Output is correct
9 Correct 0 ms 384 KB Output is correct
10 Correct 0 ms 384 KB Output is correct
11 Correct 0 ms 384 KB Output is correct
12 Correct 0 ms 384 KB Output is correct
13 Correct 0 ms 384 KB Output is correct
14 Correct 0 ms 384 KB Output is correct
15 Correct 0 ms 384 KB Output is correct
16 Correct 0 ms 384 KB Output is correct
17 Correct 0 ms 384 KB Output is correct
18 Correct 1 ms 384 KB Output is correct
19 Correct 0 ms 384 KB Output is correct
20 Correct 0 ms 384 KB Output is correct
21 Correct 0 ms 384 KB Output is correct
22 Correct 1 ms 384 KB Output is correct
23 Correct 0 ms 384 KB Output is correct
24 Correct 1 ms 384 KB Output is correct
25 Correct 1 ms 384 KB Output is correct
26 Correct 1 ms 384 KB Output is correct
27 Correct 1 ms 384 KB Output is correct
28 Correct 1 ms 384 KB Output is correct
29 Correct 0 ms 384 KB Output is correct
30 Correct 0 ms 384 KB Output is correct
31 Correct 1 ms 384 KB Output is correct
32 Correct 0 ms 384 KB Output is correct

Subtask #2
40.0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 0 ms 384 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 0 ms 384 KB Output is correct
6 Correct 0 ms 384 KB Output is correct
7 Correct 0 ms 384 KB Output is correct
8 Correct 0 ms 384 KB Output is correct
9 Correct 0 ms 384 KB Output is correct
10 Correct 0 ms 384 KB Output is correct
11 Correct 0 ms 384 KB Output is correct
12 Correct 0 ms 384 KB Output is correct
13 Correct 0 ms 384 KB Output is correct
14 Correct 0 ms 384 KB Output is correct
15 Correct 0 ms 384 KB Output is correct
16 Correct 0 ms 384 KB Output is correct
17 Correct 0 ms 384 KB Output is correct
18 Correct 1 ms 384 KB Output is correct
19 Correct 0 ms 384 KB Output is correct
20 Correct 0 ms 384 KB Output is correct
21 Correct 0 ms 384 KB Output is correct
22 Correct 1 ms 384 KB Output is correct
23 Correct 0 ms 384 KB Output is correct
24 Correct 1 ms 384 KB Output is correct
25 Correct 1 ms 384 KB Output is correct
26 Correct 1 ms 384 KB Output is correct
27 Correct 1 ms 384 KB Output is correct
28 Correct 1 ms 384 KB Output is correct
29 Correct 0 ms 384 KB Output is correct
30 Correct 0 ms 384 KB Output is correct
31 Correct 1 ms 384 KB Output is correct
32 Correct 0 ms 384 KB Output is correct
33 Correct 0 ms 384 KB Output is correct
34 Correct 1 ms 384 KB Output is correct
35 Correct 0 ms 384 KB Output is correct
36 Correct 0 ms 384 KB Output is correct
37 Correct 1 ms 384 KB Output is correct
38 Correct 1 ms 384 KB Output is correct
39 Correct 0 ms 384 KB Output is correct
40 Correct 1 ms 384 KB Output is correct
41 Correct 0 ms 384 KB Output is correct
42 Correct 0 ms 384 KB Output is correct
43 Correct 1 ms 384 KB Output is correct
44 Correct 0 ms 384 KB Output is correct
45 Correct 1 ms 384 KB Output is correct
46 Correct 0 ms 384 KB Output is correct
47 Correct 0 ms 384 KB Output is correct
48 Correct 0 ms 384 KB Output is correct
49 Correct 1 ms 384 KB Output is correct
50 Correct 0 ms 384 KB Output is correct
51 Correct 0 ms 384 KB Output is correct
52 Correct 0 ms 384 KB Output is correct
53 Correct 1 ms 384 KB Output is correct
54 Correct 0 ms 384 KB Output is correct
55 Correct 0 ms 384 KB Output is correct
56 Correct 1 ms 384 KB Output is correct
57 Correct 0 ms 384 KB Output is correct
58 Correct 0 ms 384 KB Output is correct
59 Correct 1 ms 384 KB Output is correct
60 Correct 0 ms 384 KB Output is correct
61 Correct 0 ms 384 KB Output is correct
62 Correct 1 ms 384 KB Output is correct

Subtask #3
0 / 45.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 0 ms 384 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 0 ms 384 KB Output is correct
6 Correct 0 ms 384 KB Output is correct
7 Correct 0 ms 384 KB Output is correct
8 Correct 0 ms 384 KB Output is correct
9 Correct 0 ms 384 KB Output is correct
10 Correct 0 ms 384 KB Output is correct
11 Correct 0 ms 384 KB Output is correct
12 Correct 0 ms 384 KB Output is correct
13 Correct 0 ms 384 KB Output is correct
14 Correct 0 ms 384 KB Output is correct
15 Correct 0 ms 384 KB Output is correct
16 Correct 0 ms 384 KB Output is correct
17 Correct 0 ms 384 KB Output is correct
18 Correct 1 ms 384 KB Output is correct
19 Correct 0 ms 384 KB Output is correct
20 Correct 0 ms 384 KB Output is correct
21 Correct 0 ms 384 KB Output is correct
22 Correct 1 ms 384 KB Output is correct
23 Correct 0 ms 384 KB Output is correct
24 Correct 1 ms 384 KB Output is correct
25 Correct 1 ms 384 KB Output is correct
26 Correct 1 ms 384 KB Output is correct
27 Correct 1 ms 384 KB Output is correct
28 Correct 1 ms 384 KB Output is correct
29 Correct 0 ms 384 KB Output is correct
30 Correct 0 ms 384 KB Output is correct
31 Correct 1 ms 384 KB Output is correct
32 Correct 0 ms 384 KB Output is correct
33 Correct 0 ms 384 KB Output is correct
34 Correct 1 ms 384 KB Output is correct
35 Correct 0 ms 384 KB Output is correct
36 Correct 0 ms 384 KB Output is correct
37 Correct 1 ms 384 KB Output is correct
38 Correct 1 ms 384 KB Output is correct
39 Correct 0 ms 384 KB Output is correct
40 Correct 1 ms 384 KB Output is correct
41 Correct 0 ms 384 KB Output is correct
42 Correct 0 ms 384 KB Output is correct
43 Correct 1 ms 384 KB Output is correct
44 Correct 0 ms 384 KB Output is correct
45 Correct 1 ms 384 KB Output is correct
46 Correct 0 ms 384 KB Output is correct
47 Correct 0 ms 384 KB Output is correct
48 Correct 0 ms 384 KB Output is correct
49 Correct 1 ms 384 KB Output is correct
50 Correct 0 ms 384 KB Output is correct
51 Correct 0 ms 384 KB Output is correct
52 Correct 0 ms 384 KB Output is correct
53 Correct 1 ms 384 KB Output is correct
54 Correct 0 ms 384 KB Output is correct
55 Correct 0 ms 384 KB Output is correct
56 Correct 1 ms 384 KB Output is correct
57 Correct 0 ms 384 KB Output is correct
58 Correct 0 ms 384 KB Output is correct
59 Correct 1 ms 384 KB Output is correct
60 Correct 0 ms 384 KB Output is correct
61 Correct 0 ms 384 KB Output is correct
62 Correct 1 ms 384 KB Output is correct
63 Incorrect 288 ms 16856 KB Output isn't correct
64 Halted 0 ms 0 KB -