Submission #163641

#	Time	Username	Problem	Language	Result	Execution time	Memory
163641		combi1k1	Remittance (JOI19_remittance)	C++14	0 / 100	982 ms	13016 KiB

remittance

#include<bits/stdc++.h>

using namespace std;

#define int long long

#define FOR(i,a,b)  for(int i = a ; i < b ; ++i)

double time()   {   return  1.0 * clock() / CLOCKS_PER_SEC; }

const int   N   = 1e6 + 1;

int a[N];

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

    int n;  cin >> n;

    auto reduce = [&](vector<int> num)  {
        FOR(i,0,num.size()) {
            if (time() > 0.98)  {
                cout << "No";
                exit(0);
            }
            int x = abs(num[i] % 2);
            int y = (num[i] - x) / 2;

            if (y)  {
                if (num.size() == i + 1)
                    num.push_back(0);
                num[i + 1] += y;
            }

            num[i] = x;
        }
        for(; num.size() && num.back() == 0 ; num.pop_back());

        return  num;
    };
    auto SoSanh = [&](vector<int> a,vector<int> b)  {
        if (a.size() < b.size())    return  true;
        if (b.size() < a.size())    return  false;

        reverse(a.begin(),a.end());
        reverse(b.begin(),b.end());

        FOR(i,0,a.size())   if (a[i] != b[i])
        return (a[i] < b[i]);

        return  true;
    };

    vector<int> dif;
    vector<int> num;

    FOR(i,0,n)  {
        int x;  cin >> x;
        int y;  cin >> y;

        dif.push_back(x - y);
    }
    num = reduce(dif);

    int L = 0;
    int R = 1e9;

    while (L < R)   {
        int M = (L + R) / 2;

        if (SoSanh(num,reduce(vector<int>(n,M))))
            R = M;
        else
            L = M + 1;
    }

    if (reduce(vector<int>(n,L)) != num)
        return  0 * puts("No");

    a[n - 1] = L;

    FOR(i,0,n - 1)
        a[i] = (dif[i] + a[(i + n - 1) % n]) / 2;

    FOR(i,0,n)  {
        if (a[i] < 0)   return  0 * puts("No");
        if (a[i] + a[i] - a[(i + n - 1) % n] != dif[i])
            return  0 * puts("No");
    }

    cout << "Yes";
}
/*
5
0 0
1 0
2 3
3 3
4 0
*/

Compilation message (stderr)

remittance.cpp: In lambda function:
remittance.cpp:7:39: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define FOR(i,a,b)  for(int i = a ; i < b ; ++i)
remittance.cpp:22:13:
         FOR(i,0,num.size()) {
             ~~~~~~~~~~~~~~             
remittance.cpp:22:9: note: in expansion of macro 'FOR'
         FOR(i,0,num.size()) {
         ^~~
remittance.cpp:31:32: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
                 if (num.size() == i + 1)
                     ~~~~~~~~~~~^~~~~~~~
remittance.cpp: In lambda function:
remittance.cpp:7:39: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
 #define FOR(i,a,b)  for(int i = a ; i < b ; ++i)
remittance.cpp:49:13:
         FOR(i,0,a.size())   if (a[i] != b[i])
             ~~~~~~~~~~~~               
remittance.cpp:49:9: note: in expansion of macro 'FOR'
         FOR(i,0,a.size())   if (a[i] != b[i])
         ^~~

• Subtask 1: 0 / 15
• Subtask 2: 0 / 40
• Subtask 3: 0 / 45