oj.uz

Submission #763488

# Submission time Handle Problem Language Result Execution time Memory
763488 2023-06-22T11:22:51 Z Polar_Bear_2007 Xylophone (JOI18_xylophone) C++14
0 / 100
 0 ms 208 KB 
#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; 
        }
    }

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

    foru(j, min_pos + 1, N - 1){
        ans[j] = ans[j - 1] + number[j - 1] * dau[j - 1];
        if(ans[j] == 5) 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; 
            }
        }
        
        min_pos++;
        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];
        }
    }

    foru(i, 0, N - 1) answer(i + 1, ans[i]);

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

Subtask #1
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 208 KB Output is correct
2 Incorrect 0 ms 208 KB Wrong Answer [4]
3 Halted 0 ms 0 KB -

Subtask #2
0 / 36.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 208 KB Output is correct
2 Incorrect 0 ms 208 KB Wrong Answer [4]
3 Halted 0 ms 0 KB -

Subtask #3
0 / 53.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 208 KB Output is correct
2 Incorrect 0 ms 208 KB Wrong Answer [4]
3 Halted 0 ms 0 KB -