Submission #1001262

#	Time	Username	Problem	Language	Result	Execution time	Memory
1001262		zh_h	Stone Arranging 2 (JOI23_ho_t1)	C++17	60 / 100	2043 ms	32484 KiB

Main

#include <bits/stdc++.h>
#define ll long long int
#define pb push_back
using namespace std;

int main(){
    int n;
    cin >> n;

    set<int> s;
    vector<int> v(n+1);

    for(int i = 1; i <= n; i ++){
        cin >> v[i];
        s.insert(v[i]);
    }

    map<int, int> m;
    map<int, int> m2;
    
    int cur=1;
    for(auto i : s){
        m[i] = cur;
        m2[cur] = i;
        cur++;
    }

    vector<int> ap(n+1, 0);

    for(int i = 1; i <= n; i ++){
        auto it = m.find(v[i]);
        if(ap[it->second] != 0){
            // cout << ap[it->second] << " " << i << endl << endl;
            int color = 0;
            for(int j = ap[it->second]; j < i; j ++){
                if(v[j] != color){
                    auto it2 = m.find(v[j]);
                    ap[it2->second] = 0;
                    v[j] = v[i];
                    color = v[j];
                }
                
            }
        }
        ap[it->second] = i;

        // cout << "i: " << i << endl;
        // for(int i = 0; i < ap.size(); i ++){
        //     cout << i << ": " << ap[i] << endl;
        // }
        // cout << endl;
    }

    // for(int i = 0; i < ap.size(); i ++){
    //     cout << i << ": " << ap[i] << endl;
    // }

    vector<pair<int, int>> ans;
    for(int i = 0; i < ap.size(); i ++){
        
        if(ap[i] != 0){
            auto it = m2.find(i);
            ans.pb({ap[i], it->second});
        }
    }
    sort(ans.begin(), ans.end());

    // for(int i = 0; i < ans.size(); i ++){
    //     cout << ans[i].first << " " << ans[i].second << endl;
    // }

    int b4 = 0;
    for(int i = 0; i < ans.size(); i ++){
        for(int j = 0; j < ans[i].first-b4; j ++){
            cout << ans[i].second << endl;
        }
        b4 = ans[i].first;
    }
    // for(auto i : ans){
        // for(int j = 0; j < i.)
    // }
    // map<int, int> m;
	// m[1] = 7;
	// m[2] = 3;
	// m[3] = 2;
	// m[4] = 5;
	// m[5] = 1;

    // auto it = m.find(3);
    // cout << it->first << " " <<  it->second;
    

    // for(int i = 1; i <= n; i ++){
    //     int temp;
    //     cin >> temp;
    //     v[i] = temp;
    //     s.insert(temp);
    //     // if(!ap[temp].empty()){
    //     //     for(auto j : ap[temp]){cout << j << " ";} cout << endl;
    //     //    ap[temp].insert(i); 
    //     // }
    //     // else{
    //         // for(int j = *ap[temp].begin(); j <= i; j ++){
    //         //     // ap[temp].insert(j); //* appearance of temp should include the positions of the new "temps"
    //         //     // ap[v[j]].erase(j); //* the appearance of v[j] in position j should be erased
    //         //     v[j] = temp; //* change the value of v[j]
    //         //     cout << j << " ";
    //         // }
    //         // cout << endl;
    //     // }
    // }
    

    // cout << endl;
    // for(int i = 1; i <= n; i ++){
    //     cout << v[i] << endl;
    // }

    
    //* find the first time when the number appear
    //* change the range into a color
    //! BUT how to change the other colors?
    //? should the finding part also use segment tree?
    //? so the leaves of the tree is the colors?
    //? how about other notes? an on/off button?

    //?


    
}

Compilation message (stderr)

Main.cpp: In function 'int main()':
Main.cpp:59:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   59 |     for(int i = 0; i < ap.size(); i ++){
      |                    ~~^~~~~~~~~~~
Main.cpp:73:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   73 |     for(int i = 0; i < ans.size(); i ++){
      |                    ~~^~~~~~~~~~~~

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