oj.uz

답안 #364966

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
364966 2021-02-10T16:03:41 Z maozkurt 마라톤 경주 (COCI14_utrka) C++17
80 / 80
 272 ms 15468 KB 
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <ctime>
#include <iostream>
#include <algorithm>
#include <queue>
#include <map>
#include <set>
#include <vector>
#include <string>
#include <stack>
#include <numeric>
#include <cassert>

#define endl '\n'
#define sp ' '

#define pb push_back
#define mp make_pair
#define ff first
#define ss second

using namespace std;

typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;

const ll mod1 = 1e9 + 7;
const ll mod2 = 1e9 + 9;

const ll mods[] = {mod1, mod2};

ll hashit(string& s){
    ll ret = 0;
    ll cur = 30;
    int n = s.size();
    for(int i=0;i<n;i++){
        ret = (ret + s[i] * cur % mods[i%2]) % mods[i%2];
        cur = cur * 30 % mods[i%2];
    }
    return ret;
}


int main(){

    ios_base::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);cerr.tie(nullptr);
    int n;cin>>n;
    multiset<ll> arr;
    map<ll,string> hs;
    for(int i=0;i<n;i++){
        string s; cin>>s;
        ll h = hashit(s);
        hs[h] = s;
        arr.insert(h);
    }
    for(int i=0;i<n-1;i++){
        string s;cin>>s;
        ll h = hashit(s);
        arr.erase(arr.find(h));
    }
    cout << hs[*arr.begin()] << endl;

}

Subtask #1
80.0 / 80.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 2 ms 492 KB Output is correct
5 Correct 2 ms 492 KB Output is correct
6 Correct 89 ms 7916 KB Output is correct
7 Correct 155 ms 11628 KB Output is correct
8 Correct 222 ms 14224 KB Output is correct
9 Correct 272 ms 15468 KB Output is correct
10 Correct 221 ms 15468 KB Output is correct