Submission #68045

#	Time	Username	Problem	Language	Result	Execution time	Memory
68045		yusufake	Permutation Recovery (info1cup17_permutation)	C++98	100 / 100	3979 ms	288672 KiB

Main

#include<bits/stdc++.h> 
using namespace std; 

#define pb push_back
#define mp make_pair
#define st first
#define nd second

typedef long long ll; 
typedef pair < ll , ll > pp; 
const ll mod = 1610612745235283; 
const int N   = 7e4 + 4; 
const int K = 277;

vector < pp > V[N];
unordered_map < ll , bool > M[N];
pp T[N];

ll L[N],ans[N],n,u,i,j,k,x,y,t;
char s[N*10];

void f(ll &r, ll x) { r = (r + x + mod*3) % mod;  }

int main(){
    scanf("%lld",&n);
    V[0].pb( mp(0,0) ); M[0][0]=1;
    y = 0;
    for(i=1;i<=n;i++){
        scanf(" %s", s);
        u = strlen(s);
        x = 0;
        for(j=0;j<u;j++)
            x = (x*10LL + s[j]-'0') % mod;
        t = (x-y-1+mod*3) % mod;
        for(j=0;j<K;j++)
            if(M[j].find( (t - L[j] + mod) % mod ) != M[j].end() ){
                for(k=0;k<V[j].size();k++)
                    f(V[j][k].st , L[j]);
                L[j] = 0;
                for(k=0;k<V[j].size();k++)
                    if(V[j][k].st == t){
                        V[j].insert(V[j].begin() + ++k , mp(t,i));
                        break;
                    }                
                f(t,1);
                for(; k<V[j].size(); k++)
                    f(V[j][k].st,t);
                M[j].clear();
                for(auto x : V[j]) M[j][x.st] = 1;
                for(j++; j<K; j++) f(L[j],t);    
                break;
            }
        y = x;
        
        /////
        if(i>>10 != i+1>>10){
            t = 0;
            for(j=0;j<K;j++){
                for(auto x : V[j]){
                    T[++t] = mp(x.st+L[j],x.nd);
                    f(T[t].st,0);
                }
                V[j].clear();
                M[j].clear();
                L[j] = 0;
            }
            for(j=1;j<=t;j++){
                V[j>>8].pb(T[j]);
                M[j>>8][ T[j].st ] = 1;
            }
        }    
    }
    
    for(t=i=0;i<K;i++)
        for(auto x : V[i])
            ans[ x.nd ] = ++t;
    
    for(i=1;i<=n;i++)
        printf("%lld ",ans[i]-1);
    return 0;
}    

Compilation message (stderr)

permutation.cpp: In function 'int main()':
permutation.cpp:37:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
                 for(k=0;k<V[j].size();k++)
                         ~^~~~~~~~~~~~
permutation.cpp:40:26: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
                 for(k=0;k<V[j].size();k++)
                         ~^~~~~~~~~~~~
permutation.cpp:46:24: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
                 for(; k<V[j].size(); k++)
                       ~^~~~~~~~~~~~
permutation.cpp:56:22: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
         if(i>>10 != i+1>>10){
                     ~^~
permutation.cpp:25:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%lld",&n);
     ~~~~~^~~~~~~~~~~
permutation.cpp:29:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf(" %s", s);
         ~~~~~^~~~~~~~~~

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