Submission #763362

#	Time	Username	Problem	Language	Result	Execution time	Memory
763362		Polar_Bear_2007	Xylophone (JOI18_xylophone)	C++17	0 / 100	2 ms	464 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 < (int)triple.size(); j++){
        if(triple[j] == number[j + 1] + number[j]){
            dau[j + 1] = dau[j];
        }
        else{
            dau[j + 1] = -dau[j];   
        }
    }
    bool check = true;
    int cnt = 0;
    while(check){
        ans[0] = ++cnt;
        if(cnt > N) break;
        int pos_one = 0, pos_n = -1;
        for(int j = 1; j <= N - 1; j++){
            ans[j] = ans[j - 1] +  number[j - 1] * (-dau[j - 1]);
            counting[ans[j]]++;
 
            if(ans[j] == 1) pos_one = j;
            if(ans[j] == N) pos_n = j;
        }
 
        foru(j, 0, N - 1){
            if(ans[j] < 1 || ans[j] > N || counting[ans[j]] > 2 || pos_one > pos_n){
                break;
            }
            if(j == N - 1) check = false;
        }        
    }
    
    cnt = 0;
 
     while(check){
        ans[0] = ++cnt;
        if(cnt > N) break;
        int pos_one = 0, pos_n = -1;
        for(int j = 1; j <= N - 1; j++){
            ans[j] = ans[j - 1] +  number[j - 1] * dau[j - 1];
            counting[ans[j]]++;
 
            if(ans[j] == 1) pos_one = j;
            if(ans[j] == N) pos_n = j;
        }
 
        foru(j, 0, N - 1){
            if(ans[j] < 1 || ans[j] > N || counting[ans[j]] > 2 || pos_one > pos_n){
                break;
            }
            if(j == N - 1) check = false;
        }        
    }
 
    foru(j, 0, N - 1) answer(j + 1, ans[j]);
  
}
// signed main(){
//     int n;
//     cin >> n;
//     solve(n);
// }

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