제출 #522773

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
522773		Theo830	Permutation Recovery (info1cup17_permutation)	C++17	0 / 100	4 ms	588 KiB

Main

    #include <bits/stdc++.h>
    using namespace std;
    typedef unsigned long long ll;
    const ll INF = 1e9+7;
    const ll MOD = 998244353;
    typedef pair<ll,ll> ii;
    #define iii pair<ll,ii>
    #define f(i,a,b) for(ll i = a;i < b;i++)
    #define pb push_back
    #define vll vector<ll>
    #define F first
    #define S second
    #define all(x) (x).begin(), (x).end()
    ///I hope I will get uprating and don't make mistakes
    ///I will never stop programming
    ///sqrt(-1) Love C++
    ///Please don't hack me
    ///@TheofanisOrfanou Theo830
    ///Think different approaches (bs,dp,greedy,graphs,shortest paths,mst)
    ///Stay Calm
    ///Look for special cases
    ///Beware of overflow and array bounds
    ///Think the problem backwards
    ///Training
    ///form g4g
    bool isSmaller(string str1, string str2){
        int n1 = str1.length(), n2 = str2.length();

        if (n1 < n2)
            return true;
        if (n2 < n1)
            return false;

        for (int i = 0; i < n1; i++)
            if (str1[i] < str2[i])
                return true;
            else if (str1[i] > str2[i])
                return false;

        return false;
    }
    string findDiff(string str1, string str2){
        string str = "";
        if(isSmaller(str1, str2))
            return "0";
        int n1 = str1.length(), n2 = str2.length();
        reverse(str1.begin(), str1.end());
        reverse(str2.begin(), str2.end());
        int carry = 0;
        for (int i = 0; i < n2; i++) {
            int sub = ((str1[i] - '0') - (str2[i] - '0') - carry);
            if (sub < 0) {
                sub = sub + 10;
                carry = 1;
            }
            else
                carry = 0;

            str.push_back(sub + '0');
        }
        for (int i = n2; i < n1; i++) {
            int sub = ((str1[i] - '0') - carry);
            if (sub < 0) {
                sub = sub + 10;
                carry = 1;
            }
            else
                carry = 0;
            str.push_back(sub + '0');
        }
        reverse(str.begin(), str.end());
        return str;
    }
    int main(void){
        ios_base::sync_with_stdio(0);
        cin.tie(0);
        ll n;
        cin>>n;
        string A[n];
        vector<string> arr;
        f(i,0,n){
            cin>>A[i];
        }
        arr.pb(A[0]);
        vll pos;
        pos.pb(0);
        string sum = A[n - 1];
        f(i,1,n){
            arr.pb(findDiff(A[i],A[i - 1]));
            pos.pb(i);
        }
        ll N = n;
        ll ans[n];
        while(n){
            bool ek = 0;
            string sumi = sum;
            for(ll j = n-1;j >= 0;j--){
                sumi = findDiff(sumi,arr[j]);
                if(findDiff(arr[j],sumi) == "1"){
                    sum = findDiff(sum,arr[j]);
                    ans[pos[j]] = n;
                    arr.erase(arr.begin() + j);
                    pos.erase(pos.begin() + j);
                    ek = 1;
                    break;
                }
            }
            if(!ek){
                while(1){

                }
            }
            n--;
        }
        f(i,0,N){
            cout<<ans[i]<<" ";
        }
        cout<<"\n";
    }

• Subtask 1: 0 / 10
• Subtask 2: 0 / 15
• Subtask 3: 0 / 18
• Subtask 4: 0 / 17
• Subtask 5: 0 / 11
• Subtask 6: 0 / 7
• Subtask 7: 0 / 16
• Subtask 8: 0 / 6