Submission #997299

#	Time	Username	Problem	Language	Result	Execution time	Memory
997299		faqinyeager	Stone Arranging 2 (JOI23_ho_t1)	C++17	0 / 100	1 ms	356 KiB

Main

#include <bits/stdc++.h>
#define ff first
#define ss second
using namespace std;
using ll = long long;

int n;
vector<int> a;

int G(vector<int>& b, ll x){
    int l = 0, r = b.size() - 1;
    while(r - l > 1){
        int mid = (l + r + 1) / 2;
        if(a[mid] >= x) r = mid;
        else l = mid;
    }
    return b[l];
}

int main(){
    cin >> n;
    
    a.resize(n);
    map<int, vector<int>> tmp;
    
    for(int i = 0; i < n; i++) cin >> a[i], tmp[a[i]].push_back(i);
        
    /*
    for(auto x: tmp){
        vector<int>& t = x.ss;
        for(auto y: t) cout << y << ' '; cout << "\n\n";
    } */
    
    int id = 0, pr = 0;
    
    vector<int> ans;
    
    while(id < n){
        int cur = a[id];
        vector<int>& positions = tmp[cur];
        
        int start = G(positions, id), end = positions.back();
        
        //cout << cur << ' ' << id << " ---> " << start << ' ' << end << '\n';
                
        for(int i = start; i <= end; i++) ans.push_back(cur);
                
        id = end + 1;
        if(id > n) break;
    }    
    
    for(int i = 0; i < n; i++) cout << ans[i] << '\n';
}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:34:17: warning: unused variable 'pr' [-Wunused-variable]
   34 |     int id = 0, pr = 0;
      |                 ^~

• Subtask 1: 0 / 25
• Subtask 2: 0 / 35
• Subtask 3: 0 / 40