Submission #763532

#	Time	Username	Problem	Language	Result	Execution time	Memory
763532		Polar_Bear_2007	Xylophone (JOI18_xylophone)	C++14	100 / 100	95 ms	496 KiB

xylophone

#ifdef MINHDEPTRAI
 
#include "/Library/Developer/CommandLineTools/usr/include/c++/v1/bits/stdc++.h"  
#include <chrono>
#define __gcd(a, b) gcd(a, b)
using namespace std ::chrono;
#else 
#include <bits/stdc++.h>
#include <xylophone.h>
#endif
 
using namespace std;
#define foru(i, a, b) for(int i = a; i <= b; ++i)
#define ford(i, a, b) for(int i = a; i >= b; --i)
#define IOS ios_base:: sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define mp(a, b) make_pair(a, b)
#define endl '\n'
const int maxN = 2e6 + 5;
const int mod = 998244353;
const long long inf = 1e17;
 
vector<int> number, triple;
 
int dau[maxN], ans[maxN], counting[maxN];

// int query(int a, int b){
//     cout << "? " <<  a << " " << b << endl;
//     int val;
//     cin >> val;
//     return val;
// }
// void answer(int i, int a){
//     cout << a << " ";
// }

void solve(int N){
    
    if(N == 2){
        answer(1, 1);
        answer(2, 2);
        return;
    }
    
    int i = 1, j = 2;
    while(j <= N){
        number.push_back(query(i, j));
        i++;
        j++;
    }
    int k = 3;
    i = 1;
    while(k <= N){
        triple.push_back(query(i, k));
        i++;
        k++;
    }
 
    dau[0] = 1;
    for(int j = 0; j <= N - 3; j++){
        if(triple[j] == number[j + 1] + number[j]){
            dau[j + 1] = dau[j];
        }
        else{
            dau[j + 1] = -dau[j];   
        }
    }
    int min_pos = 0, min_val = maxN, sum = 0, pos_five = N + 1;

    for(int j = 0; j <= N - 2; j++){
        sum += dau[j] * number[j];

        if(min_val > sum){
            min_val = sum;
            min_pos = j + 1; 
        }
    }
    if(min_pos == 1) min_pos = 0;

    ans[min_pos] = 1;
    ford(j, min_pos - 1, 0){
        ans[j] = ans[j + 1] +  number[j] * (- dau[j]);
        if(ans[j] == N) pos_five = j;
    }

    foru(j, min_pos + 1, N - 1){
        ans[j] = ans[j - 1] + number[j - 1] * dau[j - 1];
        if(ans[j] == N) pos_five = j;
    }

    if(min_pos > pos_five){
        min_pos = 0, min_val = maxN, sum = 0;
        foru(i, 0, N - 2) dau[i] = -dau[i];



        for(int j = 0; j <= N - 2; j++){
            sum += dau[j] * number[j];

            if(min_val > sum){
                min_val = sum;
                min_pos = j + 1; 
            }
        }
        if(min_pos == 1) min_pos = 0;
    
        
        ans[min_pos] = 1;
        ford(j, min_pos - 1, 0){
            ans[j] = ans[j + 1] +  number[j] * (- dau[j]);
            //cout << number[j] << " " << - dau[j] << endl;
        }

        foru(j, min_pos + 1, N - 1){
            ans[j] = ans[j - 1] + number[j - 1] *  dau[j - 1];
        }
    }
    int sum_check = 0;
    foru(i, 0, N - 1){
        sum_check += i + 1;
        sum_check -= ans[i];
    }
    if(sum_check != 0) foru(i, 0, N - 1) answer(i + 1, ans[i] + 1);
    else foru(i, 0, N - 1) answer(i + 1, ans[i]);

}
// signed main(){
//     int n;
//     cin >> n;
//     solve(n);
// }

• Subtask 1: 11 / 11
• Subtask 2: 36 / 36
• Subtask 3: 53 / 53