Submission #1001266

#	Time	Username	Problem	Language	Result	Execution time	Memory
1001266		zh_h	Stone Arranging 2 (JOI23_ho_t1)	C++17	60 / 100	2072 ms	32304 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]);
    }

    if(s.size() == n){
        for(int i = 1; i <= n; i ++){
            cout << v[i] << endl;
        }
    }

    else{

        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:18:17: warning: comparison of integer expressions of different signedness: 'std::set<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   18 |     if(s.size() == n){
      |        ~~~~~~~~~^~~~
Main.cpp:67:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   67 |         for(int i = 0; i < ap.size(); i ++){
      |                        ~~^~~~~~~~~~~
Main.cpp:81:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   81 |         for(int i = 0; i < ans.size(); i ++){
      |                        ~~^~~~~~~~~~~~

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